1015. Smallest Integer Divisible by K

At first, if K ends with digit {0, 2, 4, 5, 6, 8}, i.e., K can be divided by 2 or 5, we can't find such integer. If not, a intuitive idea is initiating the target integer number to 1 and keep the operation number = number * 10 + 1 until n can be divide by K. However, if K is very large, number will overflow. Here, we need to make use of the characteristics of modular arithmetic:

1. (a + b) % k = (a % k + b % k) % k
2. (a * b) % k = ( (a % k) * (b % k)) % k

Assume the smallest number is m = n * 10 + 1, then (n * 10 + 1) % K = 0, which means ((n % K) * (10 % k) + 1 % K ) % K = 0. Therefore, we can replace number with number % K to calculate the smallest number.

public int smallestRepunitDivByK(int K) {
    if( K % 2 == 0 || K % 5 == 0 )
	return -1;
    int base = 1, number = 1;
    while( number % K != 0 ) {
	number = (number * 10 + 1) % K;
	base++;
    }
    return base;
}