10127 - Ones

[uDebug]

"Bhagsash upopado" means nothing but "Remainder Theorem"

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.

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

is the same as doing w % 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

Now, let's employ the remainder algorithm to see if we get the same result. Note that, in this case, x1 = 4, x2 = 2, x3 = 6 and x4 = 5. The initial value of v is 0. So,

Step 1

Code: Select all

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

Step 2

Code: Select all

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

Step 3

Code: Select all

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

Step 4

Code: Select all

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

Neat, huh?

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.

[sajal2k8]

Why TLE?
#include <iostream>
#include <cstring>

using namespace std;

int main()
{
unsigned long long int a,num,count1=0,b,d=1000;
while(cin>>a)
{
if(a==1)
cout<<1<<endl;
else
{


num=111;
while(num%a!=0)
{
num=num+d;
d=d*10;
}
while(num)
{
num /= 10;
++count1;
}
cout<<count1<<endl;
d=1000;
count1=0;
}
}
return 0;
}
Thanks in advance

[lighted]

Code: Select all

Use code tags

Input

Code: Select all

9999

Output

Code: Select all

36

Your program gets TLE on this test. 36 digit number won't fit in unsigned long long. You must make mod(%) of num and count number of digits in first loop.