CareerCup

For case of divided by 3:

(1). Divide the binary stream in groups of size 4.
(2). For each group, find its decimal value and corresponding remainder. Say the remainder is r1.
(3). Find remainder for the next group. say it is r2.
(4). The remainder of these two groups would be (r1+r2)%3.
(5). Use this remainder ((r1+r2)%3) as if it is the remainder as described in (2).
(6) Repeat (3), (4), (5)

The solution can be written as (ak * 10 ^ k + .... a0) % 3 = [ak * (9,,,9 + 1) + ... + a0] % 3 = [ak + a(k - 1) + ... + a0] % 3. So we just need to add all digits of decimal of the binary number and then use the sum to module 3. Saw a similar problem in leetcode.

def remainder(binarystring, k):
    r = 0
    for c in binarystring:
        r *= 2 
        if c == '1': r += 1 
        r %= k 
    return r

assume the large number is represented as a string "11" with the MSB first
assume further the divisor (k) is represented as integer

even if python is capable of nearly unlimitted sized integers, the
remainder operation is implemented manualy

just implement the manual (paper-style) division algorith but only keep remainder this is O(n) runetime and O(1) space where n is the number of bits I assume this is the best conceivable runtime since I can't imagine how to calculate a remainder withouth touching each bit. how ever, there might be a more optimized version, using fewer divisions.

complete python code

def remainder(binarystring, k):
    r = 0
    for c in binarystring:
        r *= 2 
        if c == '1': r += 1 
        r %= k 
    return r 

print(remainder("11", 3)) # 3%3 = 0 
print(remainder("111", 3)) # 7%3 = 1
print(remainder("101", 3)) # 5%3 = 2
print(remainder("1111", 3)) #15%3 = 0
print(remainder("10000", 3)) #16%3 = 1 
print(remainder("10001", 3)) #17%3 = 2 
print(remainder("10010", 3)) #18%3 = 0
print(remainder("100010111100", 3)) #2236%3 = 1

class Main {
  public static void main(String[] args) {
    BigInteger num = new BigInteger("9620680364645634331845386726262609206982068206820281340810801411111793759");
    String s = num.toString(2);
    System.out.println(s);
    
    for (int i = 2; i <= 999; i++) {
      String str1 = num.mod(new BigInteger(Integer.toString(i))).toString();
      String str2 = "" + mod(s, i);
      if (!str1.equals(str2)) {
        System.out.println(i + ":\t" + str1 + "\t" + str2);
      }
    }
  }
  
  private static int mod(String num, int k) {
    final long maxValModK = (1L<<62) % k;
    int times = 0;
    int pos = num.length()-1;
    int res = 0;
    while (pos >= 0) {
      long factor = 1;
      long x = 0;
      while (pos >= 0 && factor != 1L<<62) {
        if (num.charAt(pos--) == '1') {
          x |= factor;
        }
        factor <<= 1;
      }
      
      x %= k;
      for (int i = 0; i < times; i++) {
        x = (x * maxValModK) % k;
      }
      
      res += x;
      res %= k;
      
      times++;
    }
    return res;
  }
}

Implement the binary divisibility rule for 3
if it is divisible, then 0 is remainder
else find the sum = 1+stream, using iteration since the stream is long
then test again using the divisibility rule,
if it is divisible then remainder is 1, else the remainder is 2