Maximum Number of Consecutive Values You Can Make

Maximum Number of Consecutive Values You Can Make

What is this problem about?

The Maximum Number of Consecutive Values You Can Make coding problem gives you an array of coin denominations. Starting from 0, you want to form every integer value from 0 upward consecutively using subsets of the coins. Find the maximum value x such that you can form all integers from 0 to x-1 (i.e., 0 through x-1 inclusive). In other words, find the first integer you cannot form.

Why is this asked in interviews?

Infosys and Amazon include this problem because it has a beautifully elegant greedy solution that's non-obvious at first glance. The algorithm — sort coins, maintain a "reach" variable representing the maximum value you can currently form, and extend reach by each coin if it's ≤ reach+1 — is a classic greedy technique that rewards candidates who can think about "what values can I currently guarantee?" incrementally.

Algorithmic pattern used

Greedy with sorted iteration: Sort the coins. Initialize reach = 0 (you can form all values from 0 to 0, i.e., just 0). For each coin c in sorted order:

• If c > reach + 1: you can't form reach + 1, so stop. Answer = reach + 1.
• If c <= reach + 1: adding coin c extends your reach to reach + c. Update reach += c.

After processing all coins, answer = reach + 1.

The key insight: if you can form all values [0, reach] and you have a coin c ≤ reach+1, you can now form all values [0, reach+c].

Example explanation

Coins: [1, 3, 4, 5]

• Sorted: [1, 3, 4, 5]. reach=0.
• Coin 1: 1 ≤ 0+1. reach = 0+1 = 1. (Can form [0,1])
• Coin 3: 3 > 1+1=2. Stop! Answer = reach+1 = 2.

You can form 0 and 1, but not 2. Answer = 2.

Coins: [1, 1, 2, 5]

• reach=0.
• Coin 1: reach=1. Coin 1: reach=2. Coin 2: 2≤3, reach=4. Coin 5: 5≤5, reach=9.
• Answer = 10.

Common mistakes candidates make

• Not sorting first: The greedy only works on sorted input. Unsorted coins can cause premature termination.
• Checking if c == reach+1 instead of c <= reach+1: Coins smaller than reach+1 also extend reach (they fill in values between 0 and reach more redundantly but also push reach higher).
• Returning reach instead of reach+1: reach is the maximum formable value; reach+1 is the first unformable value (the answer).

Interview preparation tip

For the Array Sorting Greedy interview pattern, the "reach extension" greedy is a powerful tool. It appears in problems like "jump game" variants and "coin reachability." The invariant to maintain is: "I can form all values in [0, reach]." Each sorted coin either extends this range or reveals a gap. Practice stating this invariant clearly in interviews — it demonstrates algorithmic maturity.