# 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.

Input:

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

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

```
Example:

```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();
}
}