Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach: Brute Force
4.
Approach: Efficient
5.
Implementation
6.
Analysis Of Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

Permutations of a Given Number That are Powers of 2

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

 

Introduction

As the title of this article suggests, we will be discussing the problem based on the famous data structure Strings. Strings are a sequence of characters like “abc” is a string containing ‘a’, ‘b,’ ‘c’ are the sequence of characters.

 

We will discuss a problem where we have to print all the possible permutations of the given number that are perfect power of 2.

What do you mean by permutations?

It rearranges the ordered list elements (string) into one-to-one correspondence to the list itself.

Also read, permutation of string

Let’s move to our problem statement to understand the problem better.

 

Problem Statement

We are given a string having ‘n’ digits, and our task is to print all the possible combinations of the digits in the string that are the perfect power of 2.

 

Note:

  • Print the combinations which are greater than ‘0’.

 

Example:

 

Input: “416”

Output: 3

 

Explanation:

All the permutations of the string 416 is 4,1,6,41,14,16,61,46,64,641,416,146,164,614,461.

 

We have to print the combinations which are perfect power of 2 i.e. 4,16,64.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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);
}
}

 

Output

 

Possible combinations are: 3
4
16
64

 

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

  1. 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.
     
  2. 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 StringNumber 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!!!

 

Previous article
Solve Sudoku on the Basis of the Given Irregular Regions
Next article
Least count of words required to construct a target String
Live masterclass