Easy solution in java O(N)


#1
public class Solution {
    public int power(String str) {
        StringBuilder cur = new StringBuilder();
        if(str.length() == 1 && Integer.parseInt(String.valueOf(str.charAt(0))) == 1) return 0;
        int j = 0;
        while(j <  str.length() && Integer.parseInt(String.valueOf(str.charAt(j))) == 0) {
            j++;
        }
         String newStr = str.substring(j, str.length());
        if(str.length() == 0) return 0;
        int num = 0;
        while(newStr.length() > 0 && Integer.parseInt(String.valueOf(newStr.charAt(newStr.length()-1))) % 2 == 0) {
            num =0;
            cur = new StringBuilder();
            for(int i=0;i<newStr.length();i++) {
                num = num*10 + Integer.parseInt(String.valueOf(newStr.charAt(i)));
                if(num > 1) {
                    cur.append(Integer.toString(num/2));
                    num = num%2;
                } else if(cur.length() > 0) cur.append('0');
             }
             newStr = cur.toString();
        }
        if(newStr.length() > 1 && Integer.parseInt(String.valueOf(newStr.charAt(newStr.length()-1))) % 2 != 0)
        return 0;
        if(newStr.length() == 1 && Integer.parseInt(String.valueOf(newStr.charAt(0))) == 1) return 1;
        return 0;
    }
}