package org.enricogiurin.codingchallenges.leetcode.challenge112020;

/*
Given a positive integer K, you need to find the length of the smallest positive integer N such that N is divisible by K, and N only contains the digit 1.

Return the length of N. If there is no such N, return -1.

Note: N may not fit in a 64-bit signed integer.



Example 1:

Input: K = 1
Output: 1
Explanation: The smallest answer is N = 1, which has length 1.
Example 2:

Input: K = 2
Output: -1
Explanation: There is no such positive integer N divisible by 2.
Example 3:

Input: K = 3
Output: 3
Explanation: The smallest answer is N = 111, which has length 3.


Constraints:

1 <= K <= 105
 */
//@math //@review
public class SmallestIntegerDivisibleByK {

    /*
    The article is actually claiming that "N * 10 + 1" and "remainder * 10 + 1" have the same remainder of K.
    We suppose N = K * x + R (R is the remainder), then N * 10 + 1 = (K * x + R) * 10 + 1
    So the remainder of "N * 10 + 1" is ((K * x + R) * 10 + 1) % K = (K * x * 10 + R * 10 + 1) % K = (R * 10 + 1) % K,
    which is the remainder * 10 +1 (Notice that K * x * 10 % K is always 0).
     */
    public int smallestRepunitDivByK(int K) {
        if (K % 2 == 0 || K % 5 == 0) {
            return -1;
        }
        int reminder = 0;
        for (int j = 1; j <= K; j++) {
            reminder = (reminder * 10 + 1) % K;
            System.out.printf("j: %s - reminder: %s\n", j, reminder);
            if (reminder == 0) {
                return j;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int k = 3;
        int result = new SmallestIntegerDivisibleByK().smallestRepunitDivByK(k);
        System.out.println(result);
    }
}
