## Just another WordPress.com site

### ACM UVA 10127 – Ones

This is a very easy but tricky problem. If you want to calculate the sequence of one by increasing ONE, then two thing can be happened.

1) If your data type is even long double (in C it is the highest data type), it can not hold the sequence and because of overflow you will get WA.
2) If your data type is string then you will get “time limit exceeded”. To avoid these problems we need to follow a trick here.

The Algorithm

input (it will be the input of the problem)
N=1
one=1 (in this variable finally we get how many one will be in the sequence)

loop until we find the desired answer {
if N < input
append a ‘1’.  (this the way -> N=N*10+1)
one = one + 1
k = N mod input  ( k is a variable )
do this until k = 0, otherwise N = k and repeat everything
}

Example

Let the input is 3
At first N = 1 and one  = 1

Now,
3 | 1 | but here N < input so, append a ‘1’
one = one + 1 = 2
3 | 11| 3
9
—–
2
Now, k = 2, so, N=k;
again,

3 | 2 | but here N < input so append a ‘1’
one = one + 1 = 3

3 | 21| 7
21
—–
x

So the output is variable ‘one’ which contains the value 3

Basically, this problem is a reverse version of dividing a series of ‘1’s with N. In the example above. The step by step of dividing “111” with “3” is like this:

3 |111| 37
9   => the same ‘9’ that we see above
—–
21
21  => the same ’21’ that we see above
—-
x

So, basically we just simulate this division but without spanning out the actual string of ‘1’s.

CODE

#include<iostream>
using namespace std;

int calculate(int input)
{
long int N=1;
int one=1,k;
while(1)
{
if(N<input)
{
N=N*10+1;
++one;
}
k=N%input;
if(k==0)
break;
else
N=k;
}
return one;
}

int main()
{
int N;
while(cin>>N)
cout<<calculate(N)<<endl;
return 0;
}

জানি বন্ধু তুমি বড় অভিমানী
রক্তে তোমার আগুন জ্বলে
এখনি সময় সব কিছুর solution করার
সাজিয়ে নাও তোমার তড়ে …।