Skip to main content
Talentd

Smallest Greater Multiple Made of Two Digits - Solution & Explanation

MediumPremiumFree on FleetCodeMathEnumeration4 min readAsked at: PayPal
Practice this problem

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 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 (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 <= 1000
  • 0 <= digit1 <= 9
  • 0 <= 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.

Solution

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Incremental Multiple ScanO(M log M)O(1)Simple baseline when constraints are small and implementation speed matters
Digit EnumerationO(2^n)O(1)Preferred approach when candidate numbers are limited by allowed digits

Video Solution

LeetCode 1999: Smallest Greater Multiple Made of Two Digits • AlitaCode • 21 views views

Frequently Asked Questions

Is Smallest Greater Multiple Made of Two Digits easy or hard?
The problem is rated Medium because the brute-force idea is obvious but inefficient. Recognizing that the candidate numbers can be directly generated using only two digits significantly reduces the search space and leads to the optimal solution.
Smallest Greater Multiple Made of Two Digits Python/Java solution
Implement enumeration that builds numbers from digit1 and digit2 up to a fixed digit length. For each number, verify it is greater than k and divisible by k using num % k. The same logic translates directly to Python, Java, C++, and Go with minimal changes.
How to solve Smallest Greater Multiple Made of Two Digits in O(2^n)?
Construct numbers using the two allowed digits with either recursion, iteration, or bitmask enumeration. For every generated number, skip values less than or equal to k and check num % k == 0. Track the smallest valid result among all candidates.
What is the best approach for Smallest Greater Multiple Made of Two Digits?
Digit enumeration is the most efficient strategy. Generate numbers composed only of digit1 and digit2, then check which ones are greater than k and divisible by k. Because each position has only two choices, the search space grows as 2^n and remains small for practical limits.
Is Smallest Greater Multiple Made of Two Digits asked at Google/Amazon/Meta?
Problems involving constrained number construction and divisibility appear frequently in technical interviews at companies like Google, Amazon, and Meta. While this exact problem may not appear verbatim, the enumeration and math techniques are commonly tested.
What data structure is used in Smallest Greater Multiple Made of Two Digits?
The core technique relies on enumeration rather than complex data structures. Candidates are generated using recursion, loops, or bitmasks, and simple arithmetic operations such as modulo are used for divisibility checks.
What is the time complexity of Smallest Greater Multiple Made of Two Digits?
The enumeration approach runs in O(2^n) time where n is the maximum number of digits generated. Each candidate requires a constant-time divisibility check. Space complexity stays O(1) because only a few numeric variables are stored.

Ready to solve this problem?

Practice Smallest Greater Multiple Made of Two Digits with our built-in code editor and test cases.

Practice on FleetCode
Previous

Add Two Numbers

Next

Reverse Integer