Given an integer N, the task is to find the smallest N-digit number which is a perfect fourth power.
Examples:
Input: N = 2
Output: 16
Only valid numbers are 24 = 16
and 34 = 81 but 16 is the minimum.Input: N = 3
Output: 256
44 = 256
Approach:
- Find the starting and ending numbers for the 4th power, which are calculated as start = 10^((n-1)/4) and end = 10^((n+3)/4).
- Iterate from start to end and calculate the 4th power of each number.
- If the number of digits of the 4th power is equal to n, we store that number as the answer and break out of the loop.
- Return the answer.
C++
#include<bits/stdc++.h>using namespace std;int smallest_ndigit(int n){ int start = pow(10, (n-1)/4); // Starting number for 4th power int end = pow(10, (n+3)/4); // Ending number for 4th power int ans = -1; for (int i = start; i < end; i++) { int num = pow(i, 4); if (to_string(num).length() == n) { ans = num; break; } } return ans;}int main() { int n = 2; cout << smallest_ndigit(n); return 0;} |
Java
import java.util.*;public class Main { public static int smallest_ndigit(int n) { int start = (int)Math.pow( 10, (n - 1) / 4); // Starting number for 4th power int end = (int)Math.pow( 10, (n + 3) / 4); // Ending number for 4th power int ans = -1; for (int i = start; i < end; i++) { int num = (int)Math.pow(i, 4); if (String.valueOf(num).length() == n) { ans = num; break; } } return ans; } public static void main(String[] args) { int n = 2; System.out.println(smallest_ndigit(n)); }}// This code is contributed by Prajwal Kandekar |
Python3
import mathdef smallest_ndigit(n): # Starting number for 4th power start = int(math.pow(10, (n-1)//4)) # Ending number for 4th power end = int(math.pow(10, (n+3)//4)) ans = -1 for i in range(start, end): num = int(math.pow(i, 4)) if len(str(num)) == n: ans = num break return ansif __name__ == "__main__": n = 2 print(smallest_ndigit(n)) |
C#
using System;public class GFG { public static int smallest_ndigit(int n) { // Starting number for 4th power int start = (int)Math.Pow(10, (n - 1) / 4); // Ending number for 4th power int end = (int)Math.Pow(10, (n + 3) / 4); int ans = -1; for (int i = start; i < end; i++) { int num = (int)Math.Pow(i, 4); if (num.ToString().Length == n) { ans = num; break; } } return ans; } public static void Main(string[] args) { int n = 2; Console.WriteLine(smallest_ndigit(n)); }} |
Javascript
function smallest_ndigit(n) { // Starting number for 4th power let start = Math.pow(10, Math.floor((n - 1) / 4)); // Ending number for 4th power let end = Math.pow(10, Math.ceil((n + 3) / 4)); let ans = -1; // Looping from start to end for (let i = start; i < end; i++) { let num = Math.pow(i, 4); if (num.toString().length == n) { ans = num; break; } } return ans;}// Driver codelet n = 2;console.log(smallest_ndigit(n)); |
Output
16
Time Complexity: O(log n)
Auxiliary Space: O(1)
Approach: It can be observed that for the values of N = 1, 2, 3, …, the series will go on like 1, 16, 256, 1296, 10000, 104976, 1048576, … whose Nth term will be pow(ceil( (pow(pow(10, (n – 1)), 1 / 4) ) ), 4).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the smallest n-digit// number which is a perfect fourth powerint cal(int n){ double res = pow(ceil((pow(pow(10, (n - 1)), 1 / 4) )), 4); return (int)res;}// Driver codeint main(){ int n = 1; cout << (cal(n));}// This code is contributed by Mohit Kumar |
Java
// Java implementation of the approachimport java.io.*;public class GFG{// Function to return the smallest n-digit// number which is a perfect fourth powerstatic int cal(int n){ double res = Math.pow(Math.ceil(( Math.pow(Math.pow(10, (n - 1)), 1 / 4) )), 4); return (int)res;}// Driver codepublic static void main(String[] args){ int n = 1; System.out.println(cal(n));}}// This code is contributed by CodeMech |
Python3
# Python3 implementation of the approachfrom math import *# Function to return the smallest n-digit # number which is a perfect fourth powerdef cal(n): res = pow(ceil( (pow(pow(10, (n - 1)), 1 / 4) ) ), 4) return int(res)# Driver coden = 1print(cal(n)) |
C#
// C# implementation of the approachusing System;class GFG{// Function to return the smallest n-digit// number which is a perfect fourth powerstatic int cal(int n){ double res = Math.Pow(Math.Ceiling(( Math.Pow(Math.Pow(10, (n - 1)), 1 / 4) )), 4); return (int)res;}// Driver codepublic static void Main(){ int n = 1; Console.Write(cal(n));}}// This code is contributed // by Akanksha_Rai |
Javascript
<script>// Javascript implementation of the approach// Function to return the smallest n-digit// number which is a perfect fourth powerfunction cal(n){ var res = Math.pow(Math.ceil((Math.pow(Math.pow(10, (n - 1)), 1 / 4) )), 4); return parseInt(res);}// Driver codevar n = 1;document.write(cal(n));// This code is contributed by rutvik_56.</script> |
Output
1
Time Complexity: O(log n)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
