Approach: Brute Force
The concept is to generate all powers of two at first, put them in a suitable data structure, and check if the power of 2 exists.
To determine if a string has a power of two, generate all possible permutations of strings and check if the string is or has a power of two.
The time complexity for this approach will be O(n!).
Let’s check how efficiently we can find the string with a power of 2.
Also see, Euclid GCD Algorithm
Approach: Efficient
For checking the string with a power of 2, we will be initializing an array that will store the count of decimal digits and check if the number of decimal digits in a power of two is less than or equal to the number decimal digits in the string.
Implementation
import java.util.*;
public class Solution
{
public static void Power(String s, int n)
{
//Arraylist will contain the long datatype
ArrayList<Long> ret=new ArrayList<Long>();
// count array will stores the count of each decimal digits of string s
int count[]=new int[10];
// loop to calculate the decimal digits
for(int i=0;i<n;i++)
{
count[s.charAt(i)-'0']++;
}
// We will initialize a new count1 array for checking i in range(0,10) that count1[i]>count[i]
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)
{
// Storing the value of val in temp variable
long temp=val;
int count1[]=new int[10];
// count1 has count of decimal digits in kth power of 2
while(temp>0)
{
long r=(temp%10);
// Typecasting to (int)
count1[(int)r]++;
temp/=10;
}
// checking if a power of 2 present in string s
boolean flag=true;
for(int i=0;i<10;i++)
{
if(count1[i]>count[i])
{
flag=false;
break;
}
}
// if the power of 2 present in s we add it to the arraylist
if(flag)
{
ret.add(val);
}
val*=2;
}
System.out.println("Possible combinations are: "+ret.size());
//For printing the arraylist
for(Long i:ret)
{
System.out.println(i);
}
}
public static void main(String[] args) {
String s="416";
int n=s.length();
Power(s,n);
}
}
You can also try this code with Online Java Compiler
Output
Possible combinations are: 3
4
16
64
You can also try this code with Online Java Compiler
Analysis Of Complexity
Time Complexity: O(log(2^62) * N) where N is the length of string and log(2^62) because 2^62 is max valid power in the range of Long.
Space Complexity: O(10+10), Due to count and count1 array.
Read about Bitwise Operators in C here.
FAQs
-
What is another approach to solve this problem?
The other approach uses the HashSet data structure to store the possible combinations. To check if the number is the power of 2, Bitwise operators are used.
-
What is the use of ArrayList?
ArrayList in Java is a dynamic array used for storing the elements. We can add or remove the elements anytime. It is much more flexible than the traditional array.
Key Takeaways
In this blog, we have covered the following:
- What the problem is, along with the example.
- Approach to ponder upon.
- Implementation in the Java language.
Before stepping into this problem, you can try problems similar to this concept like Permutations of a String, Number Of Permutations, and many more.
Along with this, you can use Coding Ninjas Studio for various DSA questions typically asked in interviews for more practice.
Happy Coding!!!
8+ registered 