I struggled with this problem for a few months. It didn't help that I knew nothing about this supposedly common"Remainder Theorem" (or algorithm, actually). So, here's some more light on the problem in case you're in the same boat as I was.wasifhossain wrote:"Bhagsash upopado" means nothing but "Remainder Theorem"

Let's hope that by now you've realized why the naive approach to the problem (in C / C++ / Pascal) won't work (and that this is what has brought to you to this thread). Clearly, there are going to be overflow issues.

Next, let's try to look at what the remainder algorithm's saying

Let w = x1x2...xn represent an integer w who's first digit is x1, who's second digit is x2 and who's nth digit is xn. So, if the integer w is

4265

then x1 = 4, x2 = 2, x3 = 6 and x4 = 5. Let y be an integer. We'd like to find the remainder when w is divided by y.

The first way to do this is of course, just perform the operation: w modulo y (written more succinctly as w % y). However, as we've just seen in this problem, this is not always possible (in the case where w is very large integer).

The other way is to employ remainder algorithm. Let v be an integer who's initial value is 0. What the remainder algorithm states is that performing the following operation

Code: Select all

```
for(i = 1; i <= n; i++) {
v = (v * 10 + xi) % y;
}
```

Let's take an example to make things clear. Let w = 4265 and y = 44. Clearly,

Code: Select all

`w modulo y = w % c = 4265 % 44 = 41`

Step 1

Code: Select all

`v = (v * 10 + x1) = (v * 10 + 4) % 44 = 4 % 44 = 4`

Code: Select all

`v = (v * 10 + x2) = (4 * 10 + 2) % 44 = 42 % 44 = 42`

Code: Select all

`v = (v * 10 + x3) = (42 * 10 + 6) % 44 = 426 % 44 = 30`

Code: Select all

`v = (v * 10 + x4) = (30 * 10 + 5) % 44 = 305 % 44 = 41`

The thing to note is that performing a modulo at every step helps "reduce" the size of the integer so that it doesn't grow too "large".

Armed with this knowledge, try looking at the problem again.