5

Reorder digits of a given number to make it a power of 2

 3 years ago
source link: https://www.geeksforgeeks.org/reorder-digits-of-a-given-number-to-make-it-a-power-of-2/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Improve Article

Reorder digits of a given number to make it a power of 2

  • Difficulty Level : Medium
  • Last Updated : 28 Jun, 2021

Given a positive integer N, the task is to rearrange the digits of the given integer such that the integer becomes a power of 2. If more than one solution exists, then print the smallest possible integer without leading 0. Otherwise, print -1.

Examples:

Input: N = 460 
Output: 64 
Explanation: 
64 is a power of 2, the required output is 64.

Input: 36 
Output: -1 
Explanation: 
Possible rearrangement of the integer are { 36, 63 }. 
Therefore, the required output is -1.

Approach: The idea is to generate all permutations of the digits of the given integer. For each permutation, check if the integer is a power of 2 or not. If found to be true then print the integer. Otherwise, print -1. Follow the steps below to solve the problem:

Below is the implementation of the above approach:

  • Python3
  • Javascript
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to rearrange the digits of N
// such that N become power of 2
int reorderedPowerOf2(int n)
{
// Stores digits of N
string str = to_string(n);
// Sort the string
// ascending order
sort(str.begin(), str.end());
// Stores count of digits in N
int sz = str.length();
// Generate all permutation and check if
// the permutation if power of 2 or not
do {
// Update n
n = stoi(str);
// If n is power of 2
if (n && !(n & (n - 1))) {
return n;
}
} while (next_permutation(str.begin(), str.end()));
return -1;
}
// Driver Code
int main()
{
int n = 460;
cout << reorderedPowerOf2(n);
return 0;
}
Output
64

Time Complexity: O(log10N * (log10N)!) 
Auxiliary Space: O(log10N)

Approach 2:

We will create a digit array which stores the digit count of the given number, and we will iterate through powers of 2 and check if any of the digitcount array matches with the given numbers digitcount array.

Below is the implementation of the approach:

// Java program to implement
// the above approach
import java.io.*;
import java.util.*;
class GFG {
public static int reorderedPowerOf2(int N)
{
int[] arr = digitarr(N);
// N is the given number
// arr have the digit count of N
for (int i = 0; i < 31; i++) {
// check if arr matches with any digitcount
// array of 2^i
if (Arrays.equals(arr, digitarr(1 << i)))
return (int)Math.pow(2, i);
}
return -1;
}
public static int[] digitarr(int n)
{
int[] res
= new int[10]; // stores the digit count of n
while (n > 0) {
if (n % 10 != 0) {
res[n % 10]++;
}
n /= 10;
}
return res;
}
// Driver code
public static void main(String[] args)
{
int n = 460;
System.out.print(reorderedPowerOf2(n));
}
}
Output
64

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK