Numbers ending in 3 have at least one multiple having all ones. for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such a no. , find the smallest such multiple of that number

A straight approach would be to check 11, 111, 1111 and so on to be divisible by that number.But that will not be optimal.

Let's say we have a series M(n) which is 11, 111, 1111 and so on.

So M(1) = 11, M(2) = 111 , etc

and lets assume the number we need to check the divisibility is n.

If M(i) mod n = 0, then you're done (M(i) is the answer), so let's assume it's not.

You want to find M(i+1) mod n.

Since M(i+1) = 10 * M(i) + 1, you can easily calculate

M(i+1) mod n =  (10 * (M(i) mod n) + 1) mod n

Hence the code

int count=1, rem=1;
while(rem)
{

rem= (rem*10+1)%n;

count++;
}

while(count--)
{
cout<<"1";
}