Microsoft Interview Question
SDE-2sCountry: 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;
}
}
public static void main(String args[]) throws Exception {
int K = 3;
System.out.println(isDivisibleByKInBase("1010100011", K, 2));
}
private static int isDivisibleByKInBase(String str, int K, int base) {
char c[] = new StringBuilder(str).reverse().toString().toCharArray();
int rem = 0;
for (int i = 0; i < c.length; i++) {
rem = ((((int) Math.pow(base, i) * Integer.parseInt("" + c[i])) % K) + rem) % K;
}
return rem;
}
Hi Koustav
- samwise.gamjee September 11, 2017Can you explain your algo?