1015. Smallest Integer Divisible by K

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<=10^5$

From: LeetCode
Link: 1015. Smallest Integer Divisible by K

Solution:

Ideas:

• A number made only of 1 can be built step by step using remainders:

  • 1
  • 11
  • 111
  • …

• Instead of storing the full number, keep only num % k:

  • new_rem = (old_rem * 10 + 1) % k

• If remainder becomes 0, that length is the answer.

• If k is divisible by 2 or 5, such a number cannot exist, because numbers ending in 1 are never divisible by 2 or 5.

• There are only k possible remainders (0 to k-1), so checking up to k lengths is enough.

Code:

static long long atMostKDistinct(const int* nums, int n, int k) {
    if (k < 0) return 0;

    // nums[i] is in [1, n], so we can use a direct frequency array of size n+1.
    int *freq = (int*)calloc((size_t)n + 1, sizeof(int));
    if (!freq) return 0; // out of memory fallback

    int left = 0;
    int distinct = 0;
    long long ans = 0;

    for (int right = 0; right < n; ++right) {
        int x = nums[right];
        if (freq[x] == 0) distinct++;
        freq[x]++;

        while (distinct > k) {
            int y = nums[left++];
            freq[y]--;
            if (freq[y] == 0) distinct--;
        }

        // all subarrays ending at right with start in [left..right] are valid
        ans += (right - left + 1);
    }

    free(freq);
    return ans;
}

int subarraysWithKDistinct(int* nums, int numsSize, int k) {
    // exactly k = atMost(k) - atMost(k-1)
    long long res = atMostKDistinct(nums, numsSize, k) - atMostKDistinct(nums, numsSize, k - 1);
    return (int)res; // result fits in 32-bit for given constraints
}