Solution of Light Online Judge - 1078 - Integer Divisibility

We will try the general condition of this problem . Let us consider that the problem description is as follows : " Given any integer 0 <= n <= 10000 not divisible by 2 or 5, some multiple of n is a number which in decimal notation is a sequence of 1's. How many digits are in the smallest such a multiple of n? "

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.

-----------------------------------------------------------------------

Now let us consider the solution procedure of this problem : 

Algorithm

------------

input description :
-----------------------
input (it will be the input of the problem) 
number =  2nd input
N=number 
one=1  (in this variable finally we get how many one will be in the sequence) 

while(1) {
  if N < input
    N=N*10+number
    one = one + 1
  k = N mod input  ( k is a variable )
  if( k == 0)
      terminate loop ;     
 otherwise 
        N = k and repeat this loop
}


Good Bye . Hope this procedure will help you in solving this problem . Have a better day .