Package g3101_3200.s3116_kth_smallest_amount_with_single_denomination_combination

Class Solution

java.lang.Object
g3101_3200.s3116_kth_smallest_amount_with_single_denomination_combination.Solution
public class Solution extends java.lang.Object
3116 - Kth Smallest Amount With Single Denomination Combination.

Hard

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 kth smallest amount that can be made using these coins.

Example 1:

Input: coins = [3,6,9], k = 3

Output: 9

Explanation: The given coins can make the following amounts:

Coin 3 produces multiples of 3: 3, 6, 9, 12, 15, etc.

Coin 6 produces multiples of 6: 6, 12, 18, 24, etc.

Coin 9 produces multiples of 9: 9, 18, 27, 36, etc.

All of the coins combined produce: 3, 6, 9 , 12, 15, etc.

Example 2:

Input: coins = [5,2], k = 7

Output: 12

Explanation: The given coins can make the following amounts:

Coin 5 produces multiples of 5: 5, 10, 15, 20, etc.

Coin 2 produces multiples of 2: 2, 4, 6, 8, 10, 12, etc.

All of the coins combined produce: 2, 4, 5, 6, 8, 10, 12 , 14, 15, etc.

Constraints:

  • 1 <= coins.length <= 15
  • 1 <= coins[i] <= 25
  • 1 <= k <= 2 * 109
  • coins contains pairwise distinct integers.

  • Constructor Summary

    Constructors
    Constructor
    Description
    Solution()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    long
    findKthSmallest(int[] coins, int k)
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • Solution

      public Solution()

  • Method Details

    • findKthSmallest

      public long findKthSmallest(int[] coins, int k)