LeetCode 2952: Minimum Number of Coins to be Added Solution

Master LeetCode problem 2952 (Minimum Number of Coins to be Added), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2952. Minimum Number of Coins to be Added

Medium

Array Greedy Sorting

Problem Explanation

Explanation

To solve this problem, we need to find the minimum number of coins that need to be added to the given array coins so that every integer in the range [1, target] is obtainable. We can approach this problem by iterating through the given coins and maintaining a reachable range. We keep track of the maximum reachable value using the current coins. If there is a gap between the maximum reachable value and the next coin value, we need to add a new coin at that gap to extend the reachable range.

Sort the given coins array.
Initialize maxReach as 0 to represent the maximum reachable value using the current coins.
For each coin in the sorted array:
- If the current coin value is greater than maxReach + 1, we need to add a coin at the gap maxReach + 1 to extend the reachable range.
- Update maxReach to include the current coin value.
Return the total number of coins added to fill the gaps.

Time Complexity: O(n log n) due to sorting, where n is the number of coins. Space Complexity: O(1) as we are using constant extra space.

Solution Code

import java.util.Arrays;

class Solution {
    public int minAdditionCoins(int[] coins, int target) {
        Arrays.sort(coins);
        int maxReach = 0;
        int addedCoins = 0;
        
        for (int coin : coins) {
            if (coin > maxReach + 1) {
                addedCoins++;
                maxReach += maxReach + 1;
            } else {
                maxReach += coin;
            }
            
            if (maxReach >= target) {
                return addedCoins;
            }
        }
        
        while (maxReach < target) {
            addedCoins++;
            maxReach += maxReach + 1;
        }
        
        return addedCoins;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2952 (Minimum Number of Coins to be Added)?

This page provides optimized solutions for LeetCode problem 2952 (Minimum Number of Coins to be Added) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2952 (Minimum Number of Coins to be Added)?

The time complexity for LeetCode 2952 (Minimum Number of Coins to be Added) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2952 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2952 in Java, C++, or Python.

Back to LeetCode Solutions