CareerCup

Hi Koustav

Can you explain your algo?

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

I think this should work.

Go over all the digits one by one in the binary number given. As you scan the number, keep track of the count of even place 1's and odd place 1's.

Finally remainder will be odd count - even count. If -ve, remained is 3+ (-ve remainder)

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;
	}

}

geeksforgeeks.org/dfa-based-division/

#include<bits/stdc++.h>
using namespace std;
int main(){
	
string s;
 cin>>s;
 int len=s.length();
 // consider s[0] as msb and s[len-1] as lsb 
 
 int rem=0;
 for(int i=0;i<len;i++){
 	 if(s[i]=='0'){
 	 	rem=rem*2;
	  }else{
	  	rem=rem*2+1;
	  }
	  rem%=3;
	  
 }
  cout<<rem<<endl;
}

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;
	}