Check if any permutation of a number without any leading zeros is a power of 2 or not
Given an integer N, the task is to check if any permutation of N without any leading zeros is a power of 2. If any such permutation of the given number exists, then print that permutation. Otherwise, print No.
Examples:
Input: N = 46
Output: 64
Explanation:
The permutation of 46 which is perfect power of 2 is 64( = 26)Input: N = 75
Output: No
Explanation:
There is no possible permutation of 75 that results in perfect power of 2.
Naive Approach: A simple solution is to generate all permutations of the number N and for each permutation, check if it is a power of 2 or not. If found to be true, print Yes. Otherwise, print No.
Time Complexity: O((log10N)!*(log10N)), where N is the given number N.
Auxiliary Space: O(1)
Efficient Approach: The count of digits for the given number and for any permutation of the given number will always be the same. Therefore, to optimize the above approach, simply check if the count of digits of the given number is equal to that of any perfect power of 2 or not. If found to be true, print that power of 2. Otherwise, print No.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; const int TEN = 10; // Function to update the frequency // array such that freq[i] stores // the frequency of digit i to n void updateFreq( int n, int freq[]) { // While there are digits // left to process while (n) { int digit = n % TEN; // Update the frequency of // the current digit freq[digit]++; // Remove the last digit n /= TEN; } } // Function that returns true if a // and b are anagrams of each other bool areAnagrams( int a, int b) { // To store the frequencies of // the digits in a and b int freqA[TEN] = { 0 }; int freqB[TEN] = { 0 }; // Update the frequency of // the digits in a updateFreq(a, freqA); // Update the frequency of // the digits in b updateFreq(b, freqB); // Match the frequencies of // the common digits for ( int i = 0; i < TEN; i++) { // If frequency differs for any // digit then the numbers are // not anagrams of each other if (freqA[i] != freqB[i]) return false ; } return true ; } // Function to check if any permutation // of a number is a power of 2 or not bool isPowerOf2( int N) { // Iterate over all possible perfect // power of 2 for ( int i = 0; i < 32; i++) { if (areAnagrams(1 << i, N)) { // Print that number cout << (1 << i); return true ; } } return false ; } // Driver Code int main() { // Given Number N int N = 46; // Function Call if (!isPowerOf2(N)) { cout << "No" ; } return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG{ static int TEN = 10 ; // Function to update the frequency // array such that freq[i] stores // the frequency of digit i to n static void updateFreq( int n, int freq[]) { // While there are digits // left to process while (n > 0 ) { int digit = n % TEN; // Update the frequency of // the current digit freq[digit]++; // Remove the last digit n /= TEN; } } // Function that returns true if a // and b are anagrams of each other static boolean areAnagrams( int a, int b) { // To store the frequencies of // the digits in a and b int freqA[] = new int [TEN]; int freqB[] = new int [TEN]; // Update the frequency of // the digits in a updateFreq(a, freqA); // Update the frequency of // the digits in b updateFreq(b, freqB); // Match the frequencies of // the common digits for ( int i = 0 ; i < TEN; i++) { // If frequency differs for any // digit then the numbers are // not anagrams of each other if (freqA[i] != freqB[i]) return false ; } return true ; } // Function to check if any permutation // of a number is a power of 2 or not static boolean isPowerOf2( int N) { // Iterate over all possible perfect // power of 2 for ( int i = 0 ; i < 32 ; i++) { if (areAnagrams( 1 << i, N)) { // Print that number System.out.print(( 1 << i)); return true ; } } return false ; } // Driver Code public static void main(String[] args) { // Given number N int N = 46 ; // Function call if (!isPowerOf2(N)) { System.out.print( "No" ); } } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach TEN = 10 # Function to update the frequency # array such that freq[i] stores # the frequency of digit i to n def updateFreq(n, freq): # While there are digits # left to process while (n): digit = n % TEN # Update the frequency of # the current digit freq[digit] + = 1 # Remove the last digit n / / = TEN # Function that returns true if a # and b are anagrams of each other def areAnagrams(a, b): # To store the frequencies of # the digits in a and b freqA = [ 0 ] * (TEN) freqB = [ 0 ] * (TEN) # Update the frequency of # the digits in a updateFreq(a, freqA) # Update the frequency of # the digits in b updateFreq(b, freqB) # Match the frequencies of # the common digits for i in range (TEN): # If frequency differs for any # digit then the numbers are # not anagrams of each other if (freqA[i] ! = freqB[i]): return False return True # Function to check if any permutation # of a number is a power of 2 or not def isPowerOf2(N): # Iterate over all possible perfect # power of 2 for i in range ( 32 ): if (areAnagrams( 1 << i, N)): # Print that number print ( 1 << i) return True return False # Driver Code # Given number N N = 46 # Function call if (isPowerOf2(N) = = 0 ): print ( "No" ) # This code is contributed by code_hunt |
C#
// C# program for // the above approach using System; class GFG{ static int TEN = 10; // Function to update the frequency // array such that freq[i] stores // the frequency of digit i to n static void updateFreq( int n, int []freq) { // While there are digits // left to process while (n > 0) { int digit = n % TEN; // Update the frequency of // the current digit freq[digit]++; // Remove the last digit n /= TEN; } } // Function that returns true if a // and b are anagrams of each other static bool areAnagrams( int a, int b) { // To store the frequencies of // the digits in a and b int []freqA = new int [TEN]; int []freqB = new int [TEN]; // Update the frequency of // the digits in a updateFreq(a, freqA); // Update the frequency of // the digits in b updateFreq(b, freqB); // Match the frequencies of // the common digits for ( int i = 0; i < TEN; i++) { // If frequency differs for any // digit then the numbers are // not anagrams of each other if (freqA[i] != freqB[i]) return false ; } return true ; } // Function to check if any // permutation of a number // is a power of 2 or not static bool isPowerOf2( int N) { // Iterate over all // possible perfect power of 2 for ( int i = 0; i < 32; i++) { if (areAnagrams(1 << i, N)) { // Print that number Console.Write((1 << i)); return true ; } } return false ; } // Driver Code public static void Main(String[] args) { // Given number N int N = 46; // Function call if (!isPowerOf2(N)) { Console.Write( "No" ); } } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript program for the above approach var TEN = 10; // Function to update the frequency // array such that freq[i] stores // the frequency of digit i to n function updateFreq(n, freq) { // While there are digits // left to process while (n) { var digit = n % TEN; // Update the frequency of // the current digit freq[digit]++; // Remove the last digit n = parseInt(n/TEN); } } // Function that returns true if a // and b are anagrams of each other function areAnagrams(a, b) { // To store the frequencies of // the digits in a and b var freqA = Array(TEN).fill(0); var freqB = Array(TEN).fill(0); // Update the frequency of // the digits in a updateFreq(a, freqA); // Update the frequency of // the digits in b updateFreq(b, freqB); // Match the frequencies of // the common digits for ( var i = 0; i < TEN; i++) { // If frequency differs for any // digit then the numbers are // not anagrams of each other if (freqA[i] != freqB[i]) return false ; } return true ; } // Function to check if any permutation // of a number is a power of 2 or not function isPowerOf2(N) { // Iterate over all possible perfect // power of 2 for ( var i = 0; i < 32; i++) { if (areAnagrams(1 << i, N)) { // Print that number document.write( (1 << i)); return true ; } } return false ; } // Driver Code // Given Number N var N = 46; // Function Call if (!isPowerOf2(N)) { document.write( "No" ); } </script> |
64
Time Complexity: O((log10N)2)
Auxiliary Space: O(1)