On a non-recursive solution

Problem was this one: Smallest Greater Multiple Made of Two Digits - LeetCode

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

Accepted

173

Submissions

287

A recursive solution will fall onto a trap where it will lean towards one branch of the "tree" only which will never end for several scenarios. Better to approach the solution with a non-recursive approach: use a queue, enqueue the candidates, ensuring that the order in which you enqueue them has always the smallest candidate atop. Code is below, cheers, ACC.

public int FindInteger(int k, int digit1, int digit2)
{
    //Special corner case
    if (digit1 == 0 && digit1 == digit2) return -1;

    Queue candidates = new Queue();

    string small = Math.Min(digit1, digit2).ToString();
    string large = Math.Max(digit1, digit2).ToString();

    candidates.Enqueue(small);
    candidates.Enqueue(large);

    while (candidates.Count > 0)
    {
        string currentCandidate = candidates.Dequeue();

        long current = Int64.Parse(currentCandidate);
        if (current >= (long)int.MaxValue) break;
        if (current > k && current % k == 0) return (int)current;

        candidates.Enqueue(currentCandidate + small);
        candidates.Enqueue(currentCandidate + large);
    }

    return -1;
}