-1

I am trying to solve "Two set bits " problem on hackerrank. Link to problem :link

Essentially I have a large string in binary and want the remainder when divided by this : 1000000007.

I am using bitset datatype for solving and the to_ullong() is causing an overflow when I convert the string to long long int.

Is there anyway to fiddle with bits of the string to get the remainder ?

Gru
  • 817
  • 13
  • 20
  • You will have to implement your own remainder function (or a way to convert to some big number library datatype that can handle bigger numbers than `unsigned long long`). – Max Langhof May 25 '18 at 14:23
  • 1
    By the way, Your link is broken – bartop May 25 '18 at 14:28
  • Please update the link so that the question is complete and one can validate the c++ code. – fjardon May 25 '18 at 14:44
  • @bartop, sry looks like it is private. – Gru May 25 '18 at 14:49
  • I Have a large string(around 1000 characters) , which is binary.Now i need to divide it by the given number as converting the binary string to decimal itself becomes too large to represent. The question said to print the remainder. – Gru May 25 '18 at 14:51

1 Answers1

0

It is hard to answer your question when the statement is not public. But using my psychic power I guess that your question is how to know the remainder of an arbitrary long bit sequence modulo K = 1000000007.

Assuming this is indeed the question, you could note your bit string as:

b_0 b_1 ... b_n

Its value is:

V = b_0*2^0 + b_1*2^1 + ... + b_n*2^n

Given the property of the modulo operation you have:

V % K = [ (b_0*2^0) % K + (b_1*2^1) % K + ... + (b_n*2^n) % K ] % K

For powers of two below K the computation is easy. For the others, you should use the modulo properties again:

V*W % K = [ (v % K) * (W % K) ] % K

For instance:

2^(1000) % K = [ (2^10) % K * ... * (2^10) % K ] % K
               \_______________  __________________/
                               \/
                           100 factors

Each modulo is easily computed and less than K making it fit for a long long.

Overall complexity will be O(n*log(n)), because you do O(log(n)) operation to compute 2^n % K, and you do this n times.

fjardon
  • 7,921
  • 22
  • 31