## Microsoft Interview Question

SDE-2s**Country:**United States

**Interview Type:**In-Person

I think this should work.

Go over all the digits of the binary number and keep a count of the number of 1's in the even place and the number of 1;'s in the odd space.

Finally the difference between the even place 1's and the odd place 1's is the remainder..

Please correct me if you have a valid situation where the logic fails

```
Time Complexity is O(n) where n is the length of input string.
static boolean isDivisible(String input) {
int noOfOnesAtOddPlace = 0;
for(int index=0; index < input.length(); index++) {
if(index%2 == 0 && input.charAt(index) == '1') {
noOfOnesAtOddPlace--;
} else if(index%2 != 0 && input.charAt(index) == '1') {
noOfOnesAtOddPlace++;
}
}
return (noOfOnesAtOddPlace%3==0);
}
```

```
boolean isDivisible(String input, int n) {
int remainder = 0;
int size = input.length();
for(int index = size-1; index >=0; index--) {
if(input.charAt(index) == '1') {
remainder = (2*remainder + 1) %n;
} else {
remainder = (2*remainder) %n;
}
}
if(remainder%n==0) {
return true;
} else {
return false;
}
}
```

- koustav.adorable September 04, 2017