Power of 2

Find if Given number is power of 2 or not.
More specifically, find if given number can be expressed as 2^k where k >= 1.

number length can be more than 64, which mean number can be greater than 2 ^ 64 (out of long long range)

return 1 if the number is a power of 2 else return 0

Input : 128
Output : 1

Method1:

Use BigInteger

Solution:

import java.math.BigInteger;

public class Solution {
    public int power(String A) {
        if (A.contains("-")) return 0;
        if (A.length() == 1 && Integer.valueOf(A) <= 1) return 0;
        BigInteger a = new BigInteger(A);
        BigInteger b = a.subtract(BigInteger.ONE);
        return a.and(b).equals(BigInteger.ZERO) ? 1 : 0;
    }
}

Method2:

Implement division by 2.
Traverse number from left digit to right.
current val = val + carry * 10
we divide current val by 2 and get the divided digit
we mod current val by 2 and get the next carry

Solution:

Time: O(n^2)
Space: O(n)

public class Solution {
    public int power(String A) {
        if (A.contains("-")) return 0;
        if (A.length() == 1 && Integer.valueOf(A) <= 1) return 0;
        String curr = A;
        while (curr.length() > 0) {
            char lastChar = curr.charAt(curr.length() - 1);
            int val = lastChar - '0';
            if (curr.length() == 1 && val == 1) {
                break;
            }
            if (val % 2 == 1) {
                return 0;
            }
            curr = divideByTwo(curr);
        }
        return 1;
    }
    
    public String divideByTwo(String A) {
        StringBuilder result = new StringBuilder();
        int i = 0;
        int carry = 0;
        while (i < A.length()) {
            char c = A.charAt(i);
            int val = c - '0';
            val = val + carry * 10;
            carry = val % 2;
            result.append(String.valueOf(val / 2));
            i ++;
        }
        while (result.length() > 0 && result.charAt(0) == '0') {
            result.deleteCharAt(0);
        }
        return result.toString();
    }
}