Given a string S consisting of N digits, the task is to print all possible combinations of the digits of the S that is a perfect power of 2.
Examples:
Input: S = “614”
Output: 4
Explanation:
All possible combinations of digit of S that are perfect power of 2 are 1, 4, 16, 64.Input: S = “6”
Output: 0
Approach: The given problem can be solved by using Backtracking. The idea is to generate all possible permutations of the string S if it is a perfect power of 2 then print it. Follow the steps below to solve the problem:
- Define a function check(int number) to check if the given number is a power of 2 and perform the following tasks:
- If the number is equal to 0, then return false.
- If the Bitwise AND of number and number-1, then return true, else return false.
- Define a function calculate(int arr[], string ans) and perform the following tasks:
- If the length of the string ans is not equal to 0 and the value of the function. check(Integer.parseInt(ans.trim())) returns true, then add this value to the HashSet H[].
- Iterate over a range [0, 10] using the variable i and perform the following tasks:
- Initialize a HashSet H[] to store the possible string numbers which are a power of 2.
- Initialize an array, say temp[] to store the frequencies of the integers in the string str.
- Iterate in a while loop till N is not equal to 0 and perform the following steps:
- Initialize the variable rem as N%10 and increase the value of temp[rem] by 1.
- Divide the value of N by 10.
- Call the function calculate(temp, “”) to find the possible permutations of the string S.
- After performing the above steps, print the HashSet as the result.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>using namespace std;// Stores the all possible generated// integers from the given stringunordered_set<int> hs;// Function to check if the// number is power of 2bool check(int number){ // If number is 0, then it // can't be a power of 2 if (number == 0) { return false; } // If the bitwise AND of n // and n-1 is 0, then only // it is a power of 2 if ((number & (number - 1)) == 0) { return true; } return false;}// Function to generate the numbersvoid calculate(int* arr, string ans){ if (ans.length() != 0) { // Checking the number if (check(stoi(ans))) { hs.insert(stoi(ans)); } } // Iterate over the range for (int i = 0; i < 10; ++i) { if (arr[i] == 0) { continue; } else { // Use the number arr[i]--; calculate(arr,(ans + to_string(i))); // Backtracking Step arr[i]++; } }}// Function to find the all possible// permutationsvoid generatePermutation(int n){ hs.clear(); // Stores the frequency of digits int temp[10]; for (int i = 0; i < 10; i++) { temp[i] = 0; } // Iterate over the number while (n != 0) { int rem = n % 10; temp[rem]++; n = n / 10; } // Function Call calculate(temp, ""); // Print the result cout << hs.size() << "\n"; for (auto i : hs) { cout << i << " "; }}int main(){ int N = 614; generatePermutation(N); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.util.*;public class GFG { // Stores the all possible generated // integers from the given string static HashSet<Integer> H = new HashSet<>(); // Function to check if the // number is power of 2 static boolean check(int number) { // If number is 0, then it // can't be a power of 2 if (number == 0) { return false; } // If the bitwise AND of n // and n-1 is 0, then only // it is a power of 2 if ((number & (number - 1)) == 0) { return true; } return false; } // Function to generate the numbers static void calculate( int arr[], String ans) { if (ans.length() != 0) { // Checking the number if (check(Integer.parseInt( ans.trim()))) { H.add(Integer.parseInt( ans.trim())); } } // Iterate over the range for (int i = 0; i < arr.length; ++i) { if (arr[i] == 0) { continue; } else { // Use the number arr[i]--; calculate(arr, ans + i); // Backtracking Step arr[i]++; } } } // Function to find the all possible // permutations static void generatePermutation(int n) { // Stores the frequency of digits int temp[] = new int[10]; // Iterate over the number while (n != 0) { int rem = n % 10; temp[rem]++; n = n / 10; } // Function Call calculate(temp, ""); // Print the result System.out.println(H.size()); System.out.println(H); } // Driver Code public static void main(String[] args) { int N = 614; generatePermutation(N); }} |
Python3
# Python3 program for the above approach# Stores the all possible generated# integers from the given stringH = set()# Function to check if the# number is power of 2def check(number): # If number is 0, then it # can't be a power of 2 if (number == 0): return False # If the bitwise AND of n # and n-1 is 0, then only # it is a power of 2 if ((number & (number - 1)) == 0): return True return False# Function to generate the numbersdef calculate(arr, ans): if (len(ans) != 0): # Checking the number if (check(int(ans))): H.add(int(ans)) # Iterate over the range for i in range(len(arr)): if (arr[i] == 0): continue else: # Use the number arr[i]-=1 calculate(arr, ans + str(i)) # Backtracking Step arr[i]+=1# Function to find the all possible# permutationsdef generatePermutation(n): # Stores the frequency of digits h = [16, 64, 1, 4] temp = [0]*(10) # Iterate over the number while (n != 0): rem = n % 10 temp[rem]+=1 n = int(n / 10) # Function Call calculate(temp, "") # Print the result print(len(H)) print(h)N = 614generatePermutation(N)# This code is contributed by divyesh072019. |
C#
using System;using System.Collections.Generic;public class GFG{ // Stores the all possible generated // integers from the given string static HashSet<int> H = new HashSet<int>(); // Function to check if the // number is power of 2 static bool check(int number) { // If number is 0, then it // can't be a power of 2 if (number == 0) { return false; } // If the bitwise AND of n // and n-1 is 0, then only // it is a power of 2 if ((number & (number - 1)) == 0) { return true; } return false; } // Function to generate the numbers static void calculate( int[] arr, String ans) { if (ans.Length != 0) { // Checking the number if (check(int.Parse( ans))) { H.Add(int.Parse( ans)); } } // Iterate over the range for (int i = 0; i < arr.Length; ++i) { if (arr[i] == 0) { continue; } else { // Use the number arr[i]--; calculate(arr, ans + i); // Backtracking Step arr[i]++; } } } // Function to find the all possible // permutations static void generatePermutation(int n) { // Stores the frequency of digits int[] temp = new int[10]; // Iterate over the number while (n != 0) { int rem = n % 10; temp[rem]++; n = n / 10; } // Function Call calculate(temp, ""); // Print the result Console.WriteLine(H.Count); foreach(var val in H){ Console.Write(val+" "); } } static public void Main (){ int N = 614; generatePermutation(N); }}// This code is contributed by maddler. |
Javascript
<script> // Javascript program for the above approach // Stores the all possible generated // integers from the given string let H = new Set(); // Function to check if the // number is power of 2 function check(number) { // If number is 0, then it // can't be a power of 2 if (number == 0) { return false; } // If the bitwise AND of n // and n-1 is 0, then only // it is a power of 2 if ((number & (number - 1)) == 0) { return true; } return false; } // Function to generate the numbers function calculate(arr, ans) { if (ans.length != 0) { // Checking the number if (check(parseInt(ans))) { H.add(parseInt(ans)); } } // Iterate over the range for (let i = 0; i < arr.length; ++i) { if (arr[i] == 0) { continue; } else { // Use the number arr[i]--; calculate(arr, ans + i); // Backtracking Step arr[i]++; } } } // Function to find the all possible // permutations function generatePermutation(n) { // Stores the frequency of digits let temp = new Array(10); let h = [16, 64, 1, 4]; temp.fill(0); // Iterate over the number while (n != 0) { let rem = n % 10; temp[rem]++; n = parseInt(n / 10, 10); } // Function Call calculate(temp, ""); // Print the result document.write(H.size + "</br>" + "["); for(let i = 0; i < h.length - 1; i++) { document.write(h[i] + ", "); } document.write(h[h.length - 1] + "]"); } let N = 614; generatePermutation(N); // This code is contributed by decode2207.</script> |
Output:
4 [16, 64, 1, 4]
Time Complexity: O(N*9N)
Auxiliary Space: O(1)
Efficient Approach: The idea is to generate all powers of two initially and store them in an appropriate data structure(“set OF CPP” in this case) and check if a power of two exits In the string
- The difficulty here is to check if power of two exits in string.
- a naive approach to check if power of two exits in string is by generating all possible permutations of strings and verifying if that string is or string has a power of 2 this approach is not recommended as time complexity is around O(n!)
- An efficient approach is to use a count array which stores the count of decimal digits and verifying if the count of each decimal digit of a power of 2 is less than or equal to count of decimal digits present in string.
C++14
#include<bits/stdc++.h>using namespace std;void calculatePower(string s,int n,set<long long>&ans){ // cnt_s is stores the count of each decimal digits of string s int cnt_s[10]={0}; // Here we calculate the count of each decimal digit of string s for(int i=0;i<n;i++) { cnt_s[s[i]-'0']++; } // our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in // cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a]) long val=2,one=1; long maxval=(one<<62); // maxval has max power of 2 in range of long // in this loop we generate powers of 2 while(val<=maxval&&val>0) { long temp=val; int cnt_a[10]={0}; // cnt_a has count of decimal digits in kth power of 2 while(temp) { long remainder=(temp%10); cnt_a[remainder]++; temp/=10; } // checking if a power of 2 present in string s bool fl=true; for(int i=0;i<10;i++) { if(cnt_a[i]>cnt_s[i]) { fl=false; break; } } // if the power of 2 present in s we add it to set if(fl) { ans.insert(val); } val*=2; }}int main() { string s="614"; int n=s.length(); // set-ans has all possible powers of 2 that are present in string set<long long>ans; calculatePower(s,n,ans); cout<<"THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: "<<ans.size()<<"\n"; for(auto i:ans) { cout<<i<<"\n"; }} |
C
#include<stdio.h>#include<string.h>void calculatePower(char s[],int n){ // cnt_s is stores the count of each decimal digits of string s int cnt_s[10]={0}; // Here we calculate the count of each decimal digit of string s for(int i=0;i<n;i++) { cnt_s[s[i]-'0']++; } // our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in // cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a]) long val=2,one=1; long maxval=(one<<62); // maxval has max power of 2 in range of long // in this loop we generate power of 2 while(val<=maxval&&val>0) { long temp=val; int cnt_a[10]={0}; // cnt_a has count of decimal digits in kth power of 2 while(temp) { long remainder=(temp%10); cnt_a[remainder]++; temp/=10; } // checking if a power of 2 present in string s int fl=1; for(int i=0;i<10;i++) { if(cnt_a[i]>cnt_s[i]) { fl=0; break; } } if(fl) { printf("%ld is present in string\n",val); } val*=2; }}int main() { char s[]="614"; int n=strlen(s); calculatePower(s,n);} |
Java
import java.util.*;public class Main{ public static void calculatePower(String s,int n) { ArrayList<Long> ans=new ArrayList<Long>(); // cnt_s is stores the count of each decimal digits of string s int cnt_s[]=new int[10]; // Here we calculate the count of each decimal digit of string s for(int i=0;i<n;i++) { cnt_s[s.charAt(i)-'0']++; } // our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in // cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a]) long value=2,one=1; long maxvalue=(one<<62); // maxval has max power of 2 in range of long // in this loop we generate powers of 2 while(value<=maxvalue && value>=0) { long temp=value; int cnt_a[]=new int[10]; // cnt_a has count of decimal digits in kth power of 2 while(temp>0) { long remainder=(temp%10); cnt_a[(int)remainder]++; temp/=10; } // checking if a power of 2 present in string s boolean fl=true; for(int i=0;i<10;i++) { if(cnt_a[i]>cnt_s[i]) { fl=false; break; } } // if the power of 2 present in s we add it to ans if(fl) { ans.add(value); } value*=2; } System.out.println("THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: "+ans.size()); for(Long i:ans) { System.out.println(i); } } public static void main(String[] args) { String s="614"; int n=s.length(); calculatePower(s,n); }} |
Python3
def calculatePower(s,n): # cnt_s is stores the count of each decimal digits of string s cnt_s=[0]*10 # Here we calculate the count of each decimal digit of string s for i in s: cnt_s[int(i)]+=1 # our main logic is to generate powers of 2 and store the count of decimal digit of powers of 2 in cnt_a i.e we check for every i in range(0,10): if(cnt_s[i]>=cnt_[a]) one=1 value=2 maxvalue=(one<<62) ans=[] # maxval has max power of 2 in range of long in this loop we generate powers of 2 while(value<=maxvalue): # cnt_a has count of decimal digits in kth power of 2 cnt_a=[0]*10 fl=True temp=value while(temp>0): remainder=temp%10 cnt_a[remainder]+=1 temp=int(temp/10) # checking if a power of 2 present in string s for i in range(0,10): if(cnt_a[i]>cnt_s[i]): fl=False break # if the power of 2 present in s we add it to ans if(fl): ans.append(value) value*=2 print("THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: ",len(ans)) for i in ans: print(i)s="614"n=len(s)calculatePower(s,n) |
C#
using System;using System.Collections.Generic;public class GFG { public static void calculatePower(string s, int n) { List<long> ans = new List<long>(); // cnt_s is stores the count of each decimal digits // of string s int[] cnt_s = new int[10]; // Here we calculate the count of each decimal digit // of string s for (int i = 0; i < n; i++) { cnt_s[s[i] - '0']++; } // our main logic is to generate powers of 2 and // store the count of decimal digit of powers of 2 // in cnt_a i.e we check for every i in range(0,10): // if(cnt_s[i]>=cnt_[a]) long value = 2, one = 1; long maxvalue = (one << 62); // maxval has max power of 2 in range of long // in this loop we generate powers of 2 while (value <= maxvalue && value >= 0) { long temp = value; int[] cnt_a = new int[10]; // cnt_a has count of decimal digits in kth // power of 2 while (temp > 0) { long remainder = (temp % 10); cnt_a[(int)remainder]++; temp /= 10; } // checking if a power of 2 present in string s bool fl = true; for (int i = 0; i < 10; i++) { if (cnt_a[i] > cnt_s[i]) { fl = false; break; } } // if the power of 2 present in s we add it to // ans if (fl) { ans.Add(value); } value *= 2; } Console.WriteLine( "THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: " + ans.Count); foreach(long i in ans) { Console.WriteLine(i); } } // Driver code public static void Main(string[] args) { string s = "614"; int n = s.Length; calculatePower(s, n); }}// This code is contributed by ukasp. |
Javascript
<script>function calculatePower(s,n){ // cnt_s is stores the count of each decimal digits of string s let cnt_s = new Array(10).fill(0) // Here we calculate the count of each decimal digit of string s for(let i of s) cnt_s[parseInt(i)] += 1 // our main logic is to generate powers of 2 and // store the count of decimal digit of powers // of 2 in cnt_a i.e we check for every i in // range(0,10): if(cnt_s[i]>=cnt_[a]) let one = 1 let value = 2 let maxvalue = (one<<62) let ans = [] // maxval has max power of 2 in range of long // in this loop we generate powers of 2 while(value <= maxvalue){ // cnt_a has count of decimal digits in kth power of 2 let cnt_a = new Array(10).fill(0) let fl = true let temp = value while(temp>0){ let remainder=temp%10 cnt_a[remainder]+=1 temp=parseInt(temp/10) } // checking if a power of 2 present in string s for(let i=0;i<10;i++){ if(cnt_a[i]>cnt_s[i]){ fl=false break } } // if the power of 2 present in s we add it to ans if(fl) ans.push(value) value*=2 } document.write("THE TOTAL POSSIBLE COMBINATIONS THAT ARE POWER OF 2 ARE: ",ans.length,"</br>") for(let i of ans) document.write(i,"</br>")}// driver codelet s = "614"let n = s.lengthcalculatePower(s,n)// This code is contributed by shinjanpatra</script> |
TIME COMPLEXITY: O(log(2^62) * N) where N is length of string and log(2^62) because 2^62 is max valid power in range of Long
AUXILIARY SPACE:O(10+10)
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!
