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

0 0 10 minutes read

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

Java

// Java program to implement
// the above approach
import 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 approach
 
 
def 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 2
 
 
def 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 Code
if __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 approach
using 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 approach
 
function 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 false
function 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 2
function 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 code
let n = 460;
document.write(reorderedPowerOf2(n));
 
 
// This code is contributed by patel2127
 
</script>

Output

Time Complexity: O(log₁₀N * (log₁₀N)!)
Auxiliary Space: O(log₁₀N)

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 code
int main()
{
    int n = 460;
    cout << reorderedPowerOf2(n);
}
 
// This code is contributed by phasing17.

Java

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

Python3

# Python3 program to implement
# the above approach
 
 
def 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 -1
 
 
def 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 code
n = 460
print(reorderedPowerOf2(n))
 
# This code is contributed by phasing17.

C#

// C# program to implement
// the above approach
using 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 code
let n = 460;
console.log(reorderedPowerOf2(n));
   
// This code is contributed by phasing17.

Output

Time Complexity: O(k*log(k)) where k=31
Auxiliary Space: O(1)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!