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:
- Convert the given integer into string say, str.
- Sort the string in ascending order.
- Generate all possible permutations of the string. For each permutation, check if the equivalent integer value of the string is a power of 2 or not. If found to be true, then print the number.
- If no such permutation of digits of the integer exists, then print -1.
Below is the implementation of the above approach:
C++
// 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 2int 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 Codeint main(){ int n = 460; cout << reorderedPowerOf2(n); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;import java.util.*;class GFG { static void swap(char[] chars, int i, int j) { char ch = chars[i]; chars[i] = chars[j]; chars[j] = ch; } static void reverse(char[] chars, int start) { for (int i = start, j = chars.length - 1; i < j; i++, j--) { swap(chars, i, j); } } // Function to find lexicographically next permutations // of a string. It returns true if the string could be // rearranged as a lexicographically greater permutation // else it returns false static boolean next_permutation(char[] chars) { // Find largest index i such // that chars[i - 1] is less than chars[i] int i = chars.length - 1; while (chars[i - 1] >= chars[i]) { // if i is first index of the string, // that means we are already at // highest possible permutation i.e. // string is sorted in desc order if (--i == 0) { return false; } } // if we reach here, substring chars[i..n) // is sorted in descending order // i.e. chars[i-1] < chars[i] >= chars[i+1] >= // chars[i+2] >= ... >= chars[n-1] // Find highest index j to the right of index i such // that chars[j] > chars[i–1] int j = chars.length - 1; while (j > i && chars[j] <= chars[i - 1]) { j--; } // swap characters at index i-1 with index j swap(chars, i - 1, j); // reverse the substring chars[i..n) and return true reverse(chars, i); return true; } // Function to rearrange the digits of N // such that N become power of 2 static int reorderedPowerOf2(int n) { // Stores digits of N String str = Integer.toString(n); char[] Str = str.toCharArray(); // Sort the string // ascending order Arrays.sort(Str); // 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 = Integer.parseInt(new String(Str)); // If n is power of 2 if (n > 0 && ((n & (n - 1)) == 0)) { return n; } } while (next_permutation(Str)); return -1; } // Driver code public static void main(String[] args) { int n = 460; System.out.print(reorderedPowerOf2(n)); }}// This code is contributed by Dharanendra L V. |
Python3
# python program to implement# the above approachdef next_permutation(): global a i = len(a) - 2 while not (i < 0 or int(a[i]) < int(a[i + 1])): i -= 1 if i < 0: return False # else j = len(a) - 1 while not (int(a[j]) > int(a[i])): j -= 1 a[i], a[j] = a[j], a[i] # swap # reverse elements from position i+1 till the end of the sequence a[i + 1:] = reversed(a[i + 1:]) return True# Function to rearrange the digits of N# such that N become power of 2def reorderedPowerOf2(n): global a # Sort the string # ascending order a = sorted(a) # Stores count of digits in N sz = len(a) # Generate all permutation and check if # the permutation if power of 2 or not while True: # Update n n = int("".join(a)) # If n is power of 2 if (n and not (n & (n - 1))): return n if not next_permutation(): break return -1# Driver Codeif __name__ == '__main__': n = 460 a = [i for i in str(n)] print(reorderedPowerOf2(n))# This code is contributed by mohit kumar 29 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG { static void swap(char[] chars, int i, int j) { char ch = chars[i]; chars[i] = chars[j]; chars[j] = ch; } static void reverse(char[] chars, int start) { for (int i = start, j = chars.Length - 1; i < j; i++, j--) { swap(chars, i, j); } } // Function to find lexicographically next permutations // of a string. It returns true if the string could be // rearranged as a lexicographically greater permutation // else it returns false static bool next_permutation(char[] chars) { // Find largest index i such // that chars[i - 1] is less than chars[i] int i = chars.Length - 1; while (chars[i - 1] >= chars[i]) { // if i is first index of the string, // that means we are already at // highest possible permutation i.e. // string is sorted in desc order if (--i == 0) { return false; } } // if we reach here, substring chars[i..n) // is sorted in descending order // i.e. chars[i-1] < chars[i] >= chars[i+1] >= // chars[i+2] >= ... >= chars[n-1] // Find highest index j to the right of index i such // that chars[j] > chars[i–1] int j = chars.Length - 1; while (j > i && chars[j] <= chars[i - 1]) { j--; } // swap characters at index i-1 with index j swap(chars, i - 1, j); // reverse the substring chars[i..n) and return true reverse(chars, i); return true; } // Function to rearrange the digits of N // such that N become power of 2 static int reorderedPowerOf2(int n) { // Stores digits of N string str = n.ToString(); char[] Str = str.ToCharArray(); // Sort the string // ascending order Array.Sort(Str); // 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 = Convert.ToInt32(new string(Str)); // If n is power of 2 if (n > 0 && ((n & (n - 1)) == 0)) { return n; } } while (next_permutation(Str)); return -1; } // Driver code static void Main() { int n = 460; Console.WriteLine(reorderedPowerOf2(n)); }}// This code is contributed by divyeshrabadiya07. |
Javascript
<script>// JavaScript program to implement// the above approachfunction swap(chars,i,j){ let ch = chars[i]; chars[i] = chars[j]; chars[j] = ch;}function reverse(chars,start){ for (let i = start, j = chars.length - 1; i < j; i++, j--) { swap(chars, i, j); }}// Function to find lexicographically next permutations// of a string. It returns true if the string could be// rearranged as a lexicographically greater permutation// else it returns falsefunction next_permutation(chars){ // Find largest index i such // that chars[i - 1] is less than chars[i] let i = chars.length - 1; while (chars[i - 1] >= chars[i]) { // if i is first index of the string, // that means we are already at // highest possible permutation i.e. // string is sorted in desc order if (--i == 0) { return false; } } // if we reach here, substring chars[i..n) // is sorted in descending order // i.e. chars[i-1] < chars[i] >= chars[i+1] >= // chars[i+2] >= ... >= chars[n-1] // Find highest index j to the right of index i such // that chars[j] > chars[i–1] let j = chars.length - 1; while (j > i && chars[j] <= chars[i - 1]) { j--; } // swap characters at index i-1 with index j swap(chars, i - 1, j); // reverse the substring chars[i..n) and return true reverse(chars, i); return true;}// Function to rearrange the digits of N// such that N become power of 2function reorderedPowerOf2(n){ // Stores digits of N let str = n.toString(); let Str = str.split(""); // Sort the string // ascending order Str.sort(); // Stores count of digits in N let sz = Str.length; // Generate all permutation and check if // the permutation if power of 2 or not do { // Update n n = parseInt((Str).join("")); // If n is power of 2 if (n > 0 && ((n & (n - 1)) == 0)) { return n; } } while (next_permutation(Str)); return -1;}// Driver codelet n = 460;document.write(reorderedPowerOf2(n));// This code is contributed by patel2127</script> |
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:
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;vector<int> digitarr(int n){ vector<int> res(10); // stores the digit count of n while (n > 0) { if (n % 10 != 0) { res[n % 10]++; } n /= 10; } return res;}int reorderedPowerOf2(int N){ vector<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 vector<int> arr1 = digitarr(1 << i); if (arr == arr1) return (int)pow(2, i); } return -1;}// Driver codeint main(){ int n = 460; cout << reorderedPowerOf2(n);}// This code is contributed by phasing17. |
Java
// Java program to implement// the above approachimport 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)); }} |
Python3
# Python3 program to implement# the above approachdef reorderedPowerOf2(N): arr = digitarr(N) # N is the given number # arr have the digit count of N for i in range(31): # check if arr matches with any digitcount # array of 2^i if (arr == digitarr(1 << i)): return pow(2, i) return -1def digitarr(n): res = [0] * 10 # stores the digit count of n while (n > 0): if (n % 10 != 0): res[n % 10] += 1 n = int(n / 10) return res # Driver coden = 460print(reorderedPowerOf2(n))# This code is contributed by phasing17. |
C#
// C# program to implement// the above approachusing System;using System.Linq;using System.Collections.Generic;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 (Enumerable.SequenceEqual(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; Console.WriteLine(reorderedPowerOf2(n)); }}// This code is contributed by phasing17. |
Javascript
// JS program to implement// the above approach function reorderedPowerOf2(N) { let arr = digitarr(N); // N is the given number // arr have the digit count of N for (var i = 0; i < 31; i++) { // check if arr matches with any digitcount // array of 2^i if (arr.join(" ") == digitarr(1 << i).join(" ") ) return Math.pow(2, i); } return -1; } function digitarr( n) { let res = new Array(10).fill(0); // stores the digit count of n while (n > 0) { if (n % 10 != 0) { res[n % 10]++; } n = Math.floor(n / 10); } return res; } // Driver codelet n = 460;console.log(reorderedPowerOf2(n)); // This code is contributed by phasing17. |
Output
64
Time Complexity: O(k*log(k)) where k=31
Auxiliary Space: O(1)
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!
