Question: CMiC | Mercer Mettl | Online Assessments (OA) | Generated Numbers (Unique Marbles)

Entering edit mode

Question 1: Generated Numbers (Unique Marbles)

Problem Statement:

You have a jar which initially contains N marbles. You can perform the following operations in any order:

Taking out A marbles from the jar.
Taking out B marbles from the jar.

Where A & B are integer values.

Your task is to find and return an integer value representing the total number of unique positive numbers of marbles that can be left behind by performing these operations, including the initial number of marbles.

Note:

The above operations can be performed any number of times and in any order, provided the jar never becomes empty (marbles left must be > 0).
The initial value of N is always included in the final count of unique marbles.

Input Specification:

input1: An integer value N, representing the initial number of marbles.
input2: An integer value A.
input3: An integer value B.

Output Specification:

Return an integer value representing the total number of unique positive numbers of marbles.

Example 1:

Input:

input1: 4

input2: 1

input3: 2

Output:

Explanation:

You can take out A=1 or B=2 marbles.

The unique values you can reach are 4 (initial), 3 (taking 1), 2 (taking 2), and 1 (taking 2 then 1, or 1 three times). Output is 4.

Example 2:

Input:

input1: 10

input2: 2

input3: 5

Output:

Explanation:

From 10, we can reach the following positive configurations by successively subtracting 2 or 5: 10, 8, 6, 4, 2, 5, 3, and 1. Output is 8.

ADD COMMENT • link

Entering edit mode

Problem1 -: Generated Numbers (Unique Marbles) Solution

Topics Involved / Prerequisites

Breadth-First Search (BFS)
State Exploration
Hash Sets / Visited Arrays

Overview

From your current number of marbles, you always have exactly two choices: subtract A or subtract B. Instead of overcomplicating it with math formulas, we can simply simulate these choices like exploring a tree. The catch? Multiple paths might lead to the same number of marbles, so we need a way to remember what we've already seen so we don't count it twice!

Approach

1. Exploring Paths (The Queue)

We can use a Queue to explore all possible marble counts step-by-step. We start by putting our initial number N into the queue. Then, one by one, we take a number out, try subtracting A and B from it, and put those new valid numbers back into the queue.

2. Remembering the Past (The Set)

To avoid recounting the same numbers or getting stuck in an infinite loop, we maintain a visited set (or a boolean array). Before we add a newly calculated marble count to our queue, we check two things: is it strictly greater than $0$, and have we not seen it yet? If both are true, we mark it as seen and add it to our queue.

Psudo Code

function getUniqueMarbles(n, a, b):
    create a queue of integers q
    create a set of integers vis
    
    q.push(n)
    vis.insert(n)
    ans = 0
    
    while q is NOT empty:
        cur = q.front()
        q.pop()
        ans = ans + 1 
        
        // Try taking out 'a' marbles
        if (cur - a > 0) AND (cur - a is NOT in vis):
            vis.insert(cur - a)
            q.push(cur - a)
            
        // Try taking out 'b' marbles
        if (cur - b > 0) AND (cur - b is NOT in vis):
            vis.insert(cur - b)
            q.push(cur - b)
            
    return ans

Time Complexity

Time: O(N) - In the worst-case scenario (e.g., A=1, B=1), we will visit every single number from N down to 1 exactly once.
Space: O(N) - To store the elements in our visited set and the queue.

ADD REPLY • link