Given a positive integer N and K where
and
. The task is to check whether any permutation of digits of N equals any power of K. If possible return “True” otherwise return “False“.
Examples:
Input: N = 96889010407, K = 7 Output: True Explanation: 96889010407 = 713 Input : N = 123456789, K = 4 Output : False
Approach: The Naive approach is to generate all permutation of digits of N and then check one by one if any of them is divisible of any power of K.
Efficient Approach: We know that total numbers of all power of K will not be more than logK(1018), for eg: if K = 2 then there will be at most 64 numbers of power of K. We generate all power of K and store it in an array.
Now we iterate all numbers from the array and check where it contains all digits of N or not.
Below is the implementation of the above approach:
C++
// CPP implementation of above approach #include <bits/stdc++.h> using namespace std; // function to check if N and K are anagrams bool isValid( long long int N, long long int K) { multiset< int > m1, m2; while (N > 0) { m1.insert(N % 10); N /= 10; } while (K > 0) { m2.insert(K % 10); K /= 10; } if (m1 == m2) return true ; return false ; } // Function to check if any permutation of N exist // such that it is some power of K string anyPermutation( long long int N, long long int K) { long long int powK[100], Limit = pow (10, 18); // generate all power of K under 10^18 powK[0] = K; int i = 1; while (powK[i - 1] * K < Limit) { powK[i] = powK[i - 1] * K; i++; } // check if any power of K is valid for ( int j = 0; j < i; j++) if (isValid(N, powK[j])) { return "True" ; } return "False" ; } // Driver program int main() { long long int N = 96889010407, K = 7; // function call to print required answer cout << anyPermutation(N, K); return 0; } // This code is written by Sanjit_Prasad |
Java
// Java implementation of above approach. import java.util.*; class GfG { // function to check if N and K are anagrams static boolean isValid( int N, int K) { HashSet<Integer> m1 = new HashSet<Integer>(); HashSet<Integer> m2 = new HashSet<Integer>(); while (N > 0 ) { m1.add(N % 10 ); N /= 10 ; } while (K > 0 ) { m2.add(K % 10 ); K /= 10 ; } if (m1.equals(m2)) { return true ; } return false ; } // Function to check if any // permutation of N exist // such that it is some power of K static String anyPermutation( int N, int K) { int powK[] = new int [ 100 + 1 ], Limit = ( int ) Math.pow( 10 , 18 ); // generate all power of K under 10^18 powK[ 0 ] = K; int i = 1 ; while (powK[i - 1 ] * K < Limit && i< 100 ) { powK[i] = powK[i - 1 ] * K; i++; } // check if any power of K is valid for ( int j = 0 ; j < i; j++) { if (isValid(N, powK[j])) { return "True" ; } } return "False" ; } // Driver code public static void main(String[] args) { int N = ( int ) 96889010407L, K = 7 ; // function call to print required answer System.out.println(anyPermutation(N, K)); } } // This code contributed by Rajput-Ji |
Python 3
# Python 3 implementation of above approach # function to check if N # and K are anagrams def isValid(N, K): m1 = [] m2 = [] while (N > 0 ) : m1.append(N % 10 ) N / / = 10 while (K > 0 ) : m2.append(K % 10 ) K / / = 10 if (m1 = = m2): return True return False # Function to check if any permutation # of N exist such that it is some power of K def anyPermutation(N, K): powK = [ 0 ] * 100 Limit = pow ( 10 , 18 ) # generate all power of # K under 10^18 powK[ 0 ] = K i = 1 while (powK[i - 1 ] * K < Limit) : powK[i] = powK[i - 1 ] * K i + = 1 # check if any power of K is valid for j in range (i): if (isValid(N, powK[j])) : return "True" return "False" # Driver Code if __name__ = = "__main__" : N = 96889010407 K = 7 # function call to print # required answer print (anyPermutation(N, K)) # This code is contributed # by ChitraNayal |
C#
// C# implementation of above approach. using System; using System.Collections.Generic; class GfG{ // Function to check if N and K are anagrams static bool isValid( long N, int K) { HashSet< long > m1 = new HashSet< long >(); HashSet< int > m2 = new HashSet< int >(); while (N > 0) { m1.Add(N % 10); N /= 10; } while (K > 0) { m2.Add(K % 10); K /= 10; } if (m1.Equals(m2)) { return true ; } return false ; } // Function to check if any // permutation of N exist // such that it is some power of K static String anyPermutation( long N, int K) { int []powK = new int [100 + 1]; int Limit = ( int ) Math.Pow(10, 18); // Generate all power // of K under 10^18 powK[0] = K; int i = 1; while (powK[i - 1] * K < Limit && i < 100) { powK[i] = powK[i - 1] * K; i++; } // Check if any power of K is valid for ( int j = 0; j < i; j++) { if (!isValid(N, powK[j])) { return "True" ; } } return "False" ; } // Driver code public static void Main(String[] args) { long N = 96889010407; int K = 7; // Function call to print required answer Console.WriteLine(anyPermutation(N, K)); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript implementation of above approach. // function to check if N and K are anagrams function isValid(N,K) { let m1 = new Set(); let m2 = new Set(); while (N > 0) { m1.add(N % 10); N = Math.floor(N/10); } while (K > 0) { m2.add(K % 10); K = Math.floor(K/10); } // To check both set are equal or not let s = new Set([...m1, ...m2]) return s.size == m1.size && s.size == m2.size } // Function to check if any // permutation of N exist // such that it is some power of K function anyPermutation(N,K) { let powK = new Array(100 + 1), Limit = (Math.pow(10, 18)); for (let i=0;i<101;i++) powK[i]=0; // generate all power of K under 10^18 powK[0] = K; let i = 1; while (powK[i - 1] * K < Limit ) { powK[i] = powK[i - 1] * K; i++; } // check if any power of K is valid for (let j = 0; j < i; j++) { if (isValid(N, powK[j])) { return "True" ; } } return "False" ; } // Driver code let N = 96889010407, K = 7; // function call to print required answer document.write(anyPermutation(N, K)); // This code is contributed by patel2127 </script> |
True
Time Complexity: O(logK(1018)2)
Auxiliary Space: O(log10N + log10K)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!