We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Smallest Greater Multiple Made of Two Digits

Number: 2141

Difficulty: Medium

Paid? Yes

Companies: PayPal

Problem Description

Given three integers k, digit1, and digit2, the task is to find the smallest integer that is strictly larger than k, is a multiple of k, and is composed only of the digits digit1 and/or digit2. If such an integer does not exist or if it exceeds the 32-bit signed integer limit (2^31 - 1), return -1.

Key Insights

  • The answer must be a multiple of k and built using only a fixed set of at most two digits.
  • Since allowed digits might include 0, care must be taken not to generate numbers with leading zeros.
  • A Breadth-First Search (BFS) can be used to generate numbers in increasing order (by length and then value) that are composed solely of the allowed digits.
  • To avoid generating large numbers unnecessarily, we should check the value against the 32-bit limit during generation.
  • Using BFS ensures that when a candidate satisfying all conditions is found, it is the smallest possible answer.

Space and Time Complexity

Time Complexity: O(2^(L)) in the worst-case scenario where L is the length (number of digits) of the final answer. Since k and digits are small, practical performance is acceptable. Space Complexity: O(2^(L)) for storing the numbers in the queue during BFS.

Solution

We use a BFS approach:

  1. Determine the unique allowed digits from digit1 and digit2.
  2. Initialize the BFS queue with non-zero allowed digits (to avoid leading zeros).
  3. For each number string in the queue:
    • Convert it to an integer; if the integer is greater than k, a multiple of k, and <= 2^31 - 1, return it.
    • Append each allowed digit to generate the next level of numbers.
  4. If no valid number is generated before the integer limit, return -1.

This method guarantees that the first valid number found is the smallest possible one satisfying all conditions.

Code Solutions

# Python solution using BFS

from collections import deque

def smallest_greater_multiple(k, digit1, digit2):
    # Define the limit for a 32-bit integer
    LIMIT = 2**31 - 1
    
    # Create a sorted list of unique allowed digits (as strings)
    allowed = sorted({str(digit1), str(digit2)})
    
    # If both allowed digits are "0", no valid number can be created
    if allowed == ["0"]:
        return -1
    
    # Initialize BFS queue with allowed digits excluding "0" as starting digit
    queue = deque([d for d in allowed if d != "0"])
    
    while queue:
        number_str = queue.popleft()
        number = int(number_str)
        
        # If number exceeds the limit, skip further processing for this branch
        if number > LIMIT:
            continue
        
        # Check if the current number satisfies the conditions
        if number > k and number % k == 0:
            return number
        
        # Append allowed digits to generate new numbers
        for digit in allowed:
            new_number_str = number_str + digit
            queue.append(new_number_str)
            
    # If no valid number is found
    return -1

# Example usage:
print(smallest_greater_multiple(2, 0, 2))  # Expected output: 20
print(smallest_greater_multiple(3, 4, 2))  # Expected output: 24
print(smallest_greater_multiple(2, 0, 0))  # Expected output: -1
← Back to All Questions