kth-smallest-amount-with-single-denomination-combination

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer array <code>coins</code> representing coins of different denominations and an integer <code>k</code>.

You have an infinite number of coins of each denomination. However, you are not allowed to combine coins of different denominations.

Return the <code>kth</code> smallest amount that can be made using these coins.

&nbsp;
Example 1:

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;
">
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.
</div>

Example 2:

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;
">
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.
</div>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= coins.length &lt;= 15</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 25</code></li>
	<li><code>1 &lt;= k &lt;= 2 * 109</code></li>
	<li><code>coins</code> contains pairwise distinct integers.</li>
</ul>

findKthSmallest

Kth Smallest Amount With Single Denomination Combination

Kth Smallest Number in Multiplication Table

kth-smallest-number-in-multiplication-table

乘法表中第k小的数

Find the Number of Possible Ways for an Event

find-the-number-of-possible-ways-for-an-event

安排活动的方案数

Bit Manipulation

Array

Math

Binary Search

Combinatorics

Number Theory

给你一个整数数组 <code>coins</code> 表示不同面额的硬币，另给你一个整数 <code>k</code> 。

你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。

返回使用这些硬币能制造的 第 <code>kth</code> 小 金额。

&nbsp;

示例 1：

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;">
输入： coins = [3,6,9], k = 3

输出： 9

解释：给定的硬币可以制造以下金额： 
3元硬币产生3的倍数：3, 6, 9, 12, 15等。 
6元硬币产生6的倍数：6, 12, 18, 24等。 
9元硬币产生9的倍数：9, 18, 27, 36等。 
所有硬币合起来可以产生：3, 6, 9, 12, 15等。
</div>

示例 2：

<div class="example-block" style="
 border-color: var(--border-tertiary);
 border-left-width: 2px;
 color: var(--text-secondary);
 font-size: .875rem;
 margin-bottom: 1rem;
 margin-top: 1rem;
 overflow: visible;
 padding-left: 1rem;">
输入：coins = [5,2], k = 7

输出：12

解释：给定的硬币可以制造以下金额： 
5元硬币产生5的倍数：5, 10, 15, 20等。 
2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。 
所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。
</div>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= coins.length &lt;= 15</code></li>
	<li><code>1 &lt;= coins[i] &lt;= 25</code></li>
	<li><code>1 &lt;= k &lt;= 2 * 109</code></li>
	<li><code>coins</code> 包含两两不同的整数。</li>
</ul>