Given an integer N, the task is to find the smallest power of four greater than or equal to N.
Examples:
Input: N = 12
Output: 16
24 = 16 which is the next required
greater number after 12.Input: N = 81
Output: 81
Approach:
- Find the fourth root of the given n.
- Calculate its floor value using floor() function.
- If n is itself a power of four then return n.
- Else add 1 to the floor value.
- Return the fourth power of that number.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function to return the smallest power // of 4 greater than or equal to n int nextPowerOfFour( int n) { int x = floor ( sqrt ( sqrt (n))); // If n is itself is a power of 4 then return n if ( pow (x, 4) == n) return n; else { x = x + 1; return pow (x, 4); } } // Driver code int main() { int n = 122; printf ( "%d" , nextPowerOfFour(n)); return 0; } // This code is contributed by Sania Kumari Gupta |
C
// C implementation of above approach #include <math.h> #include <stdio.h> // Function to return the smallest power // of 4 greater than or equal to n int nextPowerOfFour( int n) { int x = floor ( sqrt ( sqrt (n))); // If n is itself is a power of 4 then return n if ( pow (x, 4) == n) return n; else { x = x + 1; return pow (x, 4); } } // Driver code int main() { int n = 122; printf ( "%d" , nextPowerOfFour(n)); return 0; } // This code is contributed by Sania Kumari Gupta |
Java
// Java implementation of above approach import java.util.*; import java.lang.Math; import java.io.*; class GFG { // Function to return the smallest power // of 4 greater than or equal to n static int nextPowerOfFour( int n) { int x = ( int )Math.floor(Math.sqrt(Math.sqrt(n))); // If n is itself is a power of 4 // then return n if (Math.pow(x, 4 ) == n) return n; else { x = x + 1 ; return ( int )Math.pow(x, 4 ); } } // Driver code public static void main (String[] args) throws java.lang.Exception { int n = 122 ; System.out.println(nextPowerOfFour(n)); } } // This code is contributed by nidhiva |
Python3
# Python3 implementation of above approach import math # Function to return the smallest power # of 4 greater than or equal to n def nextPowerOfFour(n): x = math.floor((n * * ( 1 / 2 )) * * ( 1 / 2 )); # If n is itself is a power of 4 # then return n if ((x * * 4 ) = = n): return n; else : x = x + 1 ; return (x * * 4 ); # Driver code n = 122 ; print (nextPowerOfFour(n)); # This code is contributed by Rajput-Ji |
C#
// C# implementation of above approach using System; class GFG { // Function to return the smallest power // of 4 greater than or equal to n static int nextPowerOfFour( int n) { int x = ( int )Math.Floor(Math.Sqrt(Math.Sqrt(n))); // If n is itself is a power of 4 // then return n if (Math.Pow(x, 4) == n) return n; else { x = x + 1; return ( int )Math.Pow(x, 4); } } // Driver code public static void Main () { int n = 122; Console.WriteLine(nextPowerOfFour(n)); } } // This code is contributed by anuj_67.. |
Javascript
<script> // Javascript implementation of above approach // Function to return the smallest power // of 4 greater than or equal to n function nextPowerOfFour(n) { let x = Math.floor(Math.sqrt( Math.sqrt(n))); // If n is itself is a power of 4 // then return n if (Math.pow(x, 4) == n) return n; else { x = x + 1; return Math.pow(x, 4); } } // Driver code let n = 122; document.write(nextPowerOfFour(n)); // This code is contributed by mohit kumar 29 </script> |
256
Time Complexity: O(logx) where x is sqrt(sqrt(n))
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!