Smallest Greater Multiple Made of Two Digits

Smallest Greater Multiple Made of Two Digits - Problem

Math Enumeration Medium

Given three integers k, digit1, and digit2, find the smallest integer that satisfies all of the following conditions:

The integer is larger than k
The integer is a multiple of k
The integer is comprised of only the digits digit1 and/or digit2

Return the smallest such integer. If no such integer exists or the integer exceeds the limit of a signed 32-bit integer (2³¹ - 1 = 2147483647), return -1.

Input & Output

Example 1 — Basic Case

$ Input: k = 2, digit1 = 1, digit2 = 2

› Output: 12

💡 Note: Numbers using digits 1,2: 1, 2, 11, 12, 21, 22... First number > 2 that's divisible by 2 is 12

Example 2 — Single Digit

$ Input: k = 3, digit1 = 4, digit2 = 2

› Output: 24

💡 Note: Numbers using digits 4,2: 2, 4, 22, 24, 42, 44... First number > 3 divisible by 3 is 24 (2+4=6, divisible by 3)

Example 3 — No Solution

$ Input: k = 2, digit1 = 3, digit2 = 5

› Output: -1

💡 Note: All numbers made from digits 3,5 are odd, so none can be divisible by 2

Constraints

1 ≤ k ≤ 500
0 ≤ digit1 ≤ 9
0 ≤ digit2 ≤ 9
digit1 ≠ digit2

Visualization

Tap to expand

Understanding the Visualization

Input

k=2, allowed digits: 1, 2

Generate

Build numbers using only digits 1 and 2

Check

Find first number > k that's divisible by k

Key Takeaway

🎯 Key Insight: Use BFS to systematically build numbers from allowed digits while tracking remainders to efficiently find multiples

Asked in

G Google 15 A Amazon 12 M Microsoft 8

The key insight is to use BFS to systematically generate numbers using only the allowed digits while tracking remainders modulo k. The optimal approach uses BFS with modular arithmetic to avoid integer overflow and efficiently find the smallest valid multiple. Time: O(k), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ BFS with Modular Arithmetic	O(k)	O(k)	Use BFS with remainder tracking to avoid generating large numbers
BFS Number Generation	O(2^d)	O(2^d)	Use BFS to generate numbers systematically by appending digits
Brute Force Check	O(n × log n)	O(1)	Check every number starting from k+1 until we find a valid multiple

BFS with Modular Arithmetic — Algorithm Steps

Track remainders (num % k) instead of full numbers
Use BFS to explore remainder transitions
When remainder becomes 0 and number > k, we found the answer
Avoid revisiting same remainder states

Visualization

Tap to expand

Step-by-Step Walkthrough

States

Track (remainder, number) pairs

Transitions

Append digits and update remainders

Success

Find remainder 0 with number > k

Code -

solution.c — C

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

#define MAX_QUEUE 10000

typedef struct {
    int remainder;
    long long number;
} State;

int solution(int k, int digit1, int digit2) {
    if (k == 0) return -1;
    
    long long limit = pow(2, 31) - 1;
    State queue[MAX_QUEUE];
    bool visited[10000] = {false};
    int front = 0, rear = 0;
    
    if (digit1 != 0) {
        queue[rear].remainder = digit1 % k;
        queue[rear].number = digit1;
        visited[digit1 % k] = true;
        rear++;
    }
    if (digit2 != 0 && digit2 != digit1) {
        if (!visited[digit2 % k]) {
            queue[rear].remainder = digit2 % k;
            queue[rear].number = digit2;
            visited[digit2 % k] = true;
            rear++;
        }
    }
    
    while (front < rear) {
        State current = queue[front++];
        
        if (current.remainder == 0 && current.number > k) {
            return current.number;
        }
        
        long long newNum1 = current.number * 10 + digit1;
        if (newNum1 <= limit && rear < MAX_QUEUE) {
            int newRemainder1 = newNum1 % k;
            if (!visited[newRemainder1]) {
                visited[newRemainder1] = true;
                queue[rear].remainder = newRemainder1;
                queue[rear].number = newNum1;
                rear++;
            }
        }
        
        if (digit1 != digit2) {
            long long newNum2 = current.number * 10 + digit2;
            if (newNum2 <= limit && rear < MAX_QUEUE) {
                int newRemainder2 = newNum2 % k;
                if (!visited[newRemainder2]) {
                    visited[newRemainder2] = true;
                    queue[rear].remainder = newRemainder2;
                    queue[rear].number = newNum2;
                    rear++;
                }
            }
        }
    }
    
    return -1;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(k)

At most k different remainder states to explore

✓ Linear Growth

Space Complexity

O(k)

Queue and visited set can contain at most k remainder states

✓ Linear Space

18.5K Views

Medium Frequency

~25 min Avg. Time

425 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

BFS with Modular Arithmetic — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler