package leetcode;

/**
 * https://leetcode.com/problems/reordered-power-of-2/
 */
public class Problem869 {
    public boolean reorderedPowerOf2(int N) {
        if (isPower2(N)) {
            return true;
        }
        String s = "" + N;
        return reorderedPowerOf2(s, 0);
    }

    private static boolean reorderedPowerOf2(String s, int idx) {
        if (idx >= s.length()) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            if (i == idx) {
                continue;
            }
            String newString = newString(s, i);
            if (newString.startsWith("0")) {
                continue;
            }
            int n = Integer.parseInt(newString);
            if (isPower2(n)) {
                return true;
            }
            System.out.println(newString);
        }
        return reorderedPowerOf2(s, idx + 1);
    }

    private static String newString(String s, int i) {
        String left = (i - 1 >= 0) ? s.substring(0, i) : "";
        String right = (i + 1 < s.length()) ? s.substring(i + 1) : "";
        return s.charAt(i) + left + right;
    }

    private static double log2(int n) {
        return Math.log(n) / Math.log(2);
    }

    private static boolean isPower2(int n) {
        return (Math.ceil(log2(n)) == Math.floor(log2(n)));
    }

    public static void main(String[] args) {
        Problem869 prob = new Problem869();
//        System.out.println(prob.reorderedPowerOf2(1)); // true
//        System.out.println(prob.reorderedPowerOf2(10)); // false
//        System.out.println(prob.reorderedPowerOf2(16)); // true
//        System.out.println(prob.reorderedPowerOf2(24)); // false
//        System.out.println(prob.reorderedPowerOf2(46)); // true
//        System.out.println(prob.reorderedPowerOf2(562)); // true
        System.out.println(prob.reorderedPowerOf2(821)); // true
//        System.out.println(prob.reorderedPowerOf2(128)); // true
//        System.out.println(prob.reorderedPowerOf2(152)); // true
//        System.out.println(prob.reorderedPowerOf2(512)); // true
    }
}

@@ -270,16 +270,30 @@
 werOf2(s
+.toCharArray()
 , 0);%0A  
@@ -342,23 +342,27 @@
 owerOf2(
-String 
+char%5B%5D char
 s, int i
@@ -387,19 +387,23 @@
 idx 
-%3E
+=
 = 
+char
 s.length
 ()) 
@@ -398,18 +398,16 @@
 s.length
-()
 ) %7B%0A    
@@ -418,178 +418,79 @@
     
-return false;%0A        %7D%0A        for (int i = 0; i %3C s.length(); i++) %7B%0A            if (i == idx) %7B%0A                continue;%0A            %7D%0A            String newString = 
+String newString = new String(chars);%0A//            System.out.println(
 newS
@@ -494,21 +494,16 @@
 ewString
-(s, i
 );%0A     
@@ -562,15 +562,19 @@
     
-continu
+return fals
 e;%0A 
@@ -639,36 +639,39 @@
 g);%0A            
-if (
+return 
 isPower2(n)) %7B%0A 
@@ -665,19 +665,17 @@
 ower2(n)
-) %7B
+;
 %0A       
@@ -671,32 +671,34 @@
 n);%0A        
+%7D%0A
         
 return true;
@@ -689,75 +689,81 @@
     
-return true;%0A            %7D%0A            System.out.println(newString
+for (int i = idx; i %3C chars.length; i++) %7B%0A            swap(chars, idx, i
 );%0A 
@@ -773,25 +773,16 @@
     
-%7D%0A
     
-    return 
+if (
 reor
@@ -795,16 +795,20 @@
 owerOf2(
+char
 s, idx +
@@ -814,245 +814,292 @@
 + 1)
-;
+) %7B
 %0A    
-%7D%0A%0A    private static String newString(String s, int i) %7B%0A        String left = (i - 1 %3E= 0) ? s.substring(0, i) : %22%22;%0A        String right = (i + 1 %3C s.length()) ? s.substring(i + 1) : %22%22;%0A        return s.charAt(i) + left + right
+            return true;%0A            %7D%0A            // Backtrack.%0A            swap(chars, idx, i);%0A        %7D%0A        return false;%0A    %7D%0A%0A    private static void swap(char%5B%5D chars, int i, int j) %7B%0A        char tmp = chars%5Bi%5D;%0A        chars%5Bi%5D = chars%5Bj%5D;%0A        chars%5Bj%5D = tmp
 ;%0A  
@@ -1787,24 +1787,26 @@
 )); // true%0A
+//
         Syst
@@ -2059,16 +2059,87 @@
 // true%0A
+        System.out.println(prob.reorderedPowerOf2(679213508)); // true%0A
     %7D%0A%7D%0A

Update problem 869