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 anagramsbool 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 Kstring 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 programint 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 anagramsdef 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 Kdef 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 Codeif __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 anagramsfunction 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 Kfunction 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 codelet N = 96889010407, K = 7;// function call to print required answerdocument.write(anyPermutation(N, K));// This code is contributed by patel2127</script> |
Output:
True
Time Complexity: O(logK(1018)2)
Auxiliary Space: O(log10N + log10K)
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!
