Smallest Greater Multiple Made of Two Digits - Video Solutions
LeetCode 1999: Smallest Greater Multiple Made of Two Digits
Smallest Greater Multiple Made of Two Digits - Video Solution
Watch the video solution for Smallest Greater Multiple Made of Two Digits, a medium level problem involving Math, Enumeration. This walkthrough by AlitaCode has 21 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given three integers, k, digit1, and digit2, you want to find the smallest integer that is:
- Larger than
k, - A multiple of
k, and - Comprised of only the digits
digit1and/ordigit2.
Return the smallest such integer. If no such integer exists or the integer exceeds the limit of a signed 32-bit integer (231 - 1), return -1.
Example 1:
Input: k = 2, digit1 = 0, digit2 = 2 Output: 20 Explanation: 20 is the first integer larger than 2, a multiple of 2, and comprised of only the digits 0 and/or 2.
Example 2:
Input: k = 3, digit1 = 4, digit2 = 2 Output: 24 Explanation: 24 is the first integer larger than 3, a multiple of 3, and comprised of only the digits 4 and/or 2.
Example 3:
Input: k = 2, digit1 = 0, digit2 = 0 Output: -1 Explanation: No integer meets the requirements so return -1.
Constraints:
1 <= k <= 10000 <= digit1 <= 90 <= digit2 <= 9
Approach Overview
Problem Overview: Given integers k, digit1, and digit2, you must construct the smallest integer that is strictly greater than k, divisible by k, and composed only of the two allowed digits. The challenge is generating valid candidates efficiently while keeping the number minimal.
Approach 1: Incremental Brute Force (O(M * log M) time, O(1) space)
The most direct idea is to iterate through multiples of k starting from 2 * k. For each multiple, check whether every digit belongs to the allowed set {digit1, digit2}. Digit validation is done by repeatedly extracting digits with modulo and division. This works because every valid answer must be a multiple of k. The downside is performance: if the valid number appears far away, the algorithm scans many multiples.
Approach 2: Digit Enumeration (O(2^n) time, O(1) space)
Instead of scanning all multiples, directly generate numbers formed only by digit1 and digit2. Treat each position as a binary choice between the two digits and enumerate combinations for lengths up to a small bound (for example up to 10 digits). For every generated number, skip those ≤ k, then test divisibility with num % k. Because the search space is only 2^n for length n, enumeration remains small and quickly finds the minimum valid candidate.
This approach is effectively a controlled search over the numeric space defined by the two digits. Sorting or tracking the smallest candidate ensures the result is minimal. Handling edge cases like leading zero (when one of the digits is 0) prevents invalid numbers.
Recommended for interviews: Digit enumeration is the expected approach. It shows you recognize the constrained search space created by two digits and avoid scanning unnecessary multiples. A brute force multiple scan demonstrates baseline reasoning, but enumeration highlights stronger problem‑solving with enumeration and number construction using math properties. Interviewers typically prefer the enumeration strategy because it drastically reduces candidate checks.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Incremental Multiple Scan | O(M log M) | O(1) | Simple baseline when constraints are small and implementation speed matters |
| Digit Enumeration | O(2^n) | O(1) | Preferred approach when candidate numbers are limited by allowed digits |