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;
        char[] chars = s.toCharArray();
        return reorderedPowerOf2(chars, 0);
    }

    private static boolean reorderedPowerOf2(char[] chars, int idx) {
        if (idx >= chars.length) {
            return false;
        }
        for (int i = 0; i < chars.length; i++) {
            if (i == idx) {
                continue;
            }
            swap(chars, idx, i);
            String newString = new String(chars);
            int n = Integer.parseInt(newString);

            System.out.println(newString);
            // Backtrack.
            swap(chars, idx, i);
        }
        return reorderedPowerOf2(chars, idx + 1);
    }

    private static void swap(char[] chars, int i, int j) {
        char tmp = chars[i];
        chars[i] = chars[j];
        chars[j] = tmp;
    }

    private static boolean isPower2(int n) {
        double dsqrt = Math.sqrt(n);
        int isqrt = (int) dsqrt;
        return dsqrt - isqrt == 0;
    }

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

@@ -240,48 +240,8 @@
  N;%0A
-        char%5B%5D chars = s.toCharArray();%0A
     
@@ -269,20 +269,16 @@
 owerOf2(
-char
 s, 0);%0A 
@@ -328,27 +328,23 @@
 owerOf2(
-char%5B%5D char
+String 
 s, int i
@@ -368,28 +368,24 @@
 (idx %3E= 
-char
 s.length
 ) %7B%0A    
@@ -376,16 +376,18 @@
 s.length
+()
 ) %7B%0A    
@@ -450,20 +450,16 @@
 i %3C 
-char
 s.length
 ; i+
@@ -454,16 +454,18 @@
 s.length
+()
 ; i++) %7B
@@ -541,39 +541,54 @@
             
-swap(chars, idx
+String newString = newString(s
 , i);%0A      
@@ -585,39 +585,36 @@
 i);%0A            
-String 
+if (
 newString = new 
@@ -610,29 +610,67 @@
 ring
- = new String(chars);
+.startsWith(%220%22)) %7B%0A                continue;%0A            %7D
 %0A   
@@ -715,17 +715,16 @@
 tring);%0A
-%0A
         
@@ -731,95 +731,110 @@
     
-System.out.println(newString);%0A            // Backtrack.%0A            swap(chars, idx, i
+if (isPower2(n)) %7B%0A                return true;%0A            %7D%0A            System.out.println(newString
 );%0A 
@@ -875,20 +875,16 @@
 owerOf2(
-char
 s, idx +
@@ -918,44 +918,40 @@
 tic 
-void swap(char%5B%5D chars, int i
+String newString(String s
 , int 
-j
+i
 ) %7B%0A
@@ -962,80 +962,173 @@
     
-char tmp = chars%5Bi%5D;%0A        chars%5Bi%5D = chars%5Bj%5D;%0A        chars%5Bj%5D = tmp
+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
 ;%0A  
@@ -1705,24 +1705,26 @@
 )); // true%0A
+//
         Syst
@@ -1776,16 +1776,216 @@
 // true%0A
+//        System.out.println(prob.reorderedPowerOf2(821)); // false%0A        System.out.println(prob.reorderedPowerOf2(152)); // true%0A//        System.out.println(prob.reorderedPowerOf2(512)); // true%0A
     %7D%0A%7D%0A

Update problem 869