10127 - Ones

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10127 - Ones

wasifhossain wrote:"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.
Check input and AC output for over 7,500 problems on uDebug!

sajal2k8
New poster
Posts: 16
Joined: Mon Nov 18, 2013 5:15 pm

Re: 10127 - Ones

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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10127 - Ones

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.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman