Find multiple of a number ending with 3 that has all ones. | CODING INTERVIEW ARCHIVES

Find multiple of a number ending with 3 that has all ones. | CODING INTERVIEW ARCHIVES

Sep

21

Find multiple of a number ending with 3 that has all ones.

Every number that ends with three follows a very interesting property:

"Any number ending with 3 will always have a multiple that has all 1's".
for eg, for,
       3  : 111
     13  : 111111
and so on.

Now the question is, given a number ending with 3, return this factor, or return the number of 1's in this divisor.

Now as can be seen from the examples given here, this number can be well beyond the range of normal data types like double or long long. Now the approach that immediately comes to mind is to use a user defined data structure like a linked list etc. to store this number. This could be a possible approach but would require tremendous amount of time and space. A very intelligent solution to this question comes by looking at how division works.

Approach:

Let's suppose that we knew the number(for eg. 111 in case of 3), and were supposed to find the quotient of division. How do we approach this problem?
            

• We take 1 digit from the dividend and divide it by the divisor, storing the remainder.. 
• Next we add another digit to this  remainder and continue doing these two steps until we have exhausted all the digits.

Let's see how this approach works for our example. Let's say we have a variable n that stores the remainder. We can initialize this with a 0. Everytime we need to add a new digit we simply multiply this variable by 10 and add the next digit.

Now, if we do exactly this until we can get a remainder of 0 and count the number of times we had to loop through, this count would tell us the number of 1's in the number.

For eg. for 3.
       Iteration 1:  (0*10 + 1)%3 = 1, n=1;
       Iteration 2:  (1*10 + 1)%3 = 2, n=2,
       Iteration 3:  (2*10 + 1)%3 = 0, n=0,
And that's it, we needed three iterations and hence the number would be 111 !!!

Read full article from Find multiple of a number ending with 3 that has all ones. | CODING INTERVIEW ARCHIVES