Smallest Integer Divisible by K - Practice Coding Problems

Smallest Integer Divisible by K - Problem

Given a positive integer k, you need to find the length of the smallest positive integer n such that:

n is divisible by k
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.

Input & Output

Example 1 — Basic Case

$ Input: k = 1

› Output: 1

💡 Note: The smallest integer containing only 1's that is divisible by 1 is "1" itself, which has length 1.

Example 2 — Requires Multiple 1's

$ Input: k = 3

› Output: 3

💡 Note: We need to find the smallest number with only 1's divisible by 3: 1%3=1, 11%3=2, 111%3=0. So "111" with length 3 is the answer.

Example 3 — Impossible Case

$ Input: k = 2

› Output: -1

💡 Note: Numbers containing only 1's are always odd, so they can never be divisible by 2. Return -1.

Constraints

1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Given positive integer k

Process

Find smallest number with only 1's divisible by k

Output

Return length of that number, or -1 if impossible

Key Takeaway

🎯 Key Insight: Use modular arithmetic to track remainders instead of building actual large numbers

Asked in

G Google 15 F Facebook 12

The key insight is to use modular arithmetic to avoid handling large numbers and detect cycles. If k has factors 2 or 5, no solution exists since numbers with only 1's are always odd and not divisible by 5. Best approach uses hash set with remainder tracking. Time: O(k), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Modular Arithmetic with Cycle Detection	O(k)	O(k)	Use remainders and hash set to avoid large numbers and detect cycles
Brute Force Simulation	O(k)	O(1)	Generate numbers 1, 11, 111, 1111... and check divisibility by k

Modular Arithmetic with Cycle Detection — Algorithm Steps

Check if k has factors 2 or 5 (impossible case)
Start with remainder = 1 % k
If remainder is 0, return current length
Track seen remainders to detect cycles
Update remainder = (remainder * 10 + 1) % k

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Start with remainder = 1 % k

Check Cycle

See if remainder was seen before

Update

remainder = (remainder * 10 + 1) % k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int solution(int k) {
    if (k % 2 == 0 || k % 5 == 0) {
        return -1;
    }
    
    int remainder = 1 % k;
    int length = 1;
    bool seen[1001] = {false};  // Assuming k <= 1000
    
    while (remainder != 0) {
        if (seen[remainder]) {
            return -1;  // Cycle detected
        }
        seen[remainder] = true;
        remainder = (remainder * 10 + 1) % k;
        length++;
    }
    
    return length;
}

int main() {
    int k;
    scanf("%d", &k);
    int result = solution(k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

At most k different remainders possible, so loop runs at most k times

✓ Linear Growth

Space Complexity

O(k)

Hash set stores at most k different remainders

✓ Linear Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Modular Arithmetic with Cycle Detection — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler