Got such a problem:
It is known that a binary number consists of A ones and B zeros.
Is it possible to say with certainty that some binary number composed of these numbers is divisible by N without a remainder?

For example, 7 units and 2 zeros, is it divisible by 25? You can make the number 101110111(375), it is divisible by 25.

As a solution, I see an enumeration of all possible options and checks of divisibility, but I do not fit into the time limit.Tell me, what other options are possible? Any universal sign of divisibility for binary numbers? Or just an option to sit down for a sign of Pascal?

3 Answers 3

Dynamic Programming:
F(a, b, r)=can a number composed of a single units and b zeros give the remainder of r when divided by N.
Base: F(0,0,0)=true, F(0,0, r)=false.

Recalculation: Iterative recalculation such - F(a, b, r)=>then F(a + 1, b,(2 * r + 1)% N) and F(a, b + 1,(2 * r + 1)% N) Here we know that there is a number that gives the remainder r from a units and b zeros.If we assign a 1 to it at the end, then the remainder will be(2 * r + 1)% N, and the units will be one more.Also almost ascribed to 0.

For recursive, you must first get rid of all powers of 2 in N(just count the degree, subtract it from B, divide N into all twos - In the end there must be so many zeros).

Now you can find x such that 2x=1(mod N) is the inverse of 2 modulo N.See the advanced Euclidean algorithm for this.

Further it is possible to calculate as follows(N is odd):
F(a, b, r)=F(a-1, b,(r-1) * x% N) || F(a, b-1, r * x% N).

The explanation here is also simple - the number either ends with 0 or 1.We try both options and erase the last digit.The remaining number should give the remainder(r-1) * x% N or r * x% N, respectively.

Answer: If F(A, B, 0) is true, then the number divisible by N is.To find the number, you must additionally remember which numbers were assigned to the numbers in the calculations above.
  • Thank you for your explanation! I will understand.I still weakly pull math and algorithms at this level, but I strive! – Better Bug Jul 12 '18 at 18:29
The maximum number for A + Bbit= C=2 ^(A + B) - 2 ^ B, i.e.for 9 bits this is 2 ^ 9-2 ^ 2=512-4=508

You need to find all the numbers from N to C inclusive, which are divided into N without remainder(in fact, are the product of N on the loop index from 1 to (C div N) inclusive), and check whether they are sums of non-repeating powers of two, and if so, is the number of numbers equal to the sum of the value of A .Te.check whether all the A bits are enabled.

For this case, with N=25, 508 div 25=20(iterations).It is necessary to check whether the product of the cycle index and N is the sum of A(7) numbers(non-repeating powers of two from 0 to A + B-1(8)).

Numbers(powers of two) can be precomputed and folded into an array, and get from there by index.

So the most difficult thing to write is a function that will check whether its argument is the sum of A non-repeating powers of two from 0 to A + B-1.

You do not need to check everything, you can interrupt the execution at the first positive result.

You can quickly check for a power of two through a bit comparison operation And

For example, K=13(8 + 4 + 1), then K&1=1, K&2=0, K&4=4, K&8=8.That is, if K&2 ^ i>0, then the number contains a power of two.Well, it remains to count for each number how many powers of two it contains.

Again, it is necessary to check not with all powers of two, but with the nearest lesser of K, that is, for K=28, the maximum power of two for comparison will be equal to 16.For K=50 - 32, for K=100 - 64 and etc.

It will be necessary to somehow calculate this degree, best of all lazily.Just calculating the next K, check whether it is more than the next power of two. here is a quick fix on JS

PS: the solution needs to be optimized, but it is already on its own :)
If you swap some 0 and 1 places, then, if the criterion exists, the delimit should not change.
Such N should divide any continuous sequence from units, including from one.That is it is impossible to tell that.
  • some binary number composed of these numbers is divided by N without a remainder

    in other words, “one can make a number” of this number of ones and zeros.
    – Vivacious Vendace Jul 19 '18 at 08:19