869. Reordering gives us a power of two

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

869. Reordering gives us a power of two

Given a positive integer N, we reorder the numbers in any order (including the original order), noting that the leading digit cannot be zero.

Return true if we can get a power of 2 as described above; Otherwise, return false.

Example 1:

Input: 1 Output: true

Example 2:

Input: 10 Output: false

Example 3:

Input: 16 Output: true

Example 4:

Input: 24 Output: false

Example 5:

Input: 46 Output: true

Their thinking

Try all the permutations of a number and see if each permutation forms a power of 2 (use set to hold all powers of 2).

code

class Solution {
    Set<Integer> tar=new HashSet<>();
    public boolean reorderedPowerOf2(int n) {

        for (int i=0; i<31; i++) { tar.add(1<<i);
        }
        String s=""+n;
        return dfsReorderedPowerOf2(s,new boolean[s.length()],0.new StringBuilder());

    }
    public boolean dfsReorderedPowerOf2(String s,boolean[] m,int cur,StringBuilder sb) {
        if (cur==s.length()){
             if (tar.contains(Integer.parseInt(sb.toString())))
                 return true;
            return false;
        }
        boolean f=false;
        for (int i = 0; i < m.length; i++) {
            if (m[i]||cur==0&&s.charAt(i)=='0')continue;
            m[i]=true;
            sb.append(s.charAt(i));
            f|=dfsReorderedPowerOf2(s,m,cur+1,sb);
            sb.deleteCharAt(sb.length()-1);
            m[i]=false;
        }
        returnf; }}Copy the code

To optimize the

Using bit optimization, you can determine whether it is a power of 2 directly according to n& (n-1). Only the numbers that are combined after each permutation are generated, and the permutation results are not saved using strings

class Solution {

    public boolean reorderedPowerOf2(int n) {
        String s=""+n;
        return dfsReorderedPowerOf2(s,new boolean[s.length()],0.0);

    }
    public boolean dfsReorderedPowerOf2(String s,boolean[] m,int cur,int sum) {
        if (cur==s.length()){
            
            if ((sum&(sum-1)) = =0)
                return true;
            return false;
        }
        boolean f=false;
        for (int i = 0; i < m.length; i++) {
            if (m[i]||cur==0&&s.charAt(i)=='0')continue;
            m[i]=true;
            f|=dfsReorderedPowerOf2(s,m,cur+1,sum*10+s.charAt(i)-'0');
            m[i]=false;
        }
        returnf; }}Copy the code

869. Reordering gives us a power of two