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

Kth Smallest Amount With Single Denomination Combination

Difficulty: Hard

Problem Description

You are given an integer array coins representing coins of different denominations and an integer k. You have an infinite number of coins of each denomination. However, you are not allowed to combine coins of different denominations. Return the k-th smallest amount that can be made using these coins.

Key Insights

  • Each coin denomination can create an infinite series of amounts that are multiples of that denomination.
  • The problem can be viewed as finding the k-th smallest value from an infinite set of multiples generated by the given denominations.
  • A min-heap can be utilized to efficiently retrieve the smallest amounts in increasing order.
  • The denominations can be processed independently, and the results can be combined to find the k-th smallest amount.

Space and Time Complexity

Time Complexity: O(k log n), where n is the number of coin denominations. This accounts for inserting k elements into a min-heap and extracting the smallest repeatedly. Space Complexity: O(n), where n is the number of coin denominations used for the min-heap.

Solution

The solution utilizes a min-heap (or priority queue) to keep track of the smallest multiples of the coin denominations. Initially, the smallest multiple of each coin is pushed into the heap. We then repeatedly extract the smallest element from the heap and generate the next multiple of the coin that produced it, continuing this process until we reach the k-th smallest amount.

Code Solutions

import heapq

def kthSmallest(coins, k):
    # Min-heap to store the smallest amounts
    min_heap = []
    
    # Initialize the heap with the first multiple of each coin
    for coin in coins:
        heapq.heappush(min_heap, coin)
    
    # Variable to hold the current smallest amount
    current_smallest = 0
    
    # Extract the smallest element k times
    for _ in range(k):
        current_smallest = heapq.heappop(min_heap)
        
        # Generate the next multiple of the coin that produced the current smallest
        for coin in coins:
            if current_smallest + coin <= 2 * 10**9:  # Prevent overflow
                heapq.heappush(min_heap, current_smallest + coin)
    
    return current_smallest
← Back to All Questions