Algorithm of 10127 - Ones

Problem Description Link
Algorithm

This is a very simple but tricky problem. If you want to calculate the sequence of one by increasing ONE, then two things 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) 
dividend=1
one=1 (in this variable finally we get how many one will be in the sequence)

do {
  if dividend < input
    append a '1'.  (this the way -> dividend= dividend *10+1)
    one = one + 1
  k = dividend mod input  ( k is a variable )
  do this until k = 0, otherwise dividend = k and repeat everything
}

Example

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

Now,
3 | 1 | but here dividend < input so, append a '1'
one = one + 1 = 2
3 | 11| 3
     9
   -----
     2
Now, k = 2, so, dividend =k;
again,

3 | 2 | but here dividend < 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 dividend. 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.