Facebook Pixel

3116. Kth Smallest Amount With Single Denomination Combination

HardBit ManipulationArrayMathBinary SearchCombinatoricsNumber Theory
Leetcode Link

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

Intuition

To solve the problem, we need to find the kth smallest amount of money that can be constructed using coins of distinct denominations. The key restriction here is that coins of different denominations cannot be combined to form a sum. This means for each denomination, we can form sums divisible by that denomination only, like multiples of 1, multiples of 2, and so forth.

The approach uses a combination of binary search and the inclusion-exclusion principle. Here's an intuition of why this approach works:

  1. Monotonicity: If we find an amount x that can form the desired count of combinations, any larger amount can also meet or exceed this count. This suggests that the problem has a monotonic nature, making binary search a suitable method.

  2. Counting Valid Amounts with Inclusion-Exclusion Principle: For each subset of the coins array, we determine the least common multiple (LCM) of the subset elements. The inclusion-exclusion principle allows us to account for all combinations by considering:

    • Adding counts for amounts up to a given number that match a single denomination (x/a, x/b, etc.).
    • Subtracting overlaps for amounts up to the LCM of two denomination counts, since these are counted twice.
    • Adding overlaps for amounts up to the LCM of three denominations, and so on, accounting for all possible combinations.

  3. Binary Search: Begin with a wide range, setting bounds from 1 to a very large number (10^11). The midpoint of this range is tested, using a check function which counts up how many amounts can be formed up to this midpoint using coins, comparing this count against k. Adjust the bounds based on whether the count is more or less than k to converge on the correct answer, which is the smallest x for which the count is at least k.

By implementing these ideas, we can efficiently determine the kth smallest sum for any given input scenario.

Learn more about Math, Binary Search and Combinatorics patterns.

Solution Approach

The solution employs a combination of binary search with the inclusion-exclusion principle to determine the kth smallest sum that can be created using the given coin denominations without combining different denominations. Here's a step-by-step breakdown of the approach:

  1. Binary Search:

    • We initialize a binary search over possible amounts with a range from 1 to 10^{11}. This range is chosen to be large enough to encompass any potential answer.
    • The goal is to find the smallest amount x such that check(x) returns true, meaning the number of different amounts that can be generated is at least k.

  2. Helper Function check(mx):

    • This function computes the count of distinct sums that can be formed using the coin denominations, up to the maximal value mx.
    • For each non-empty subset of coins, compute the least common multiple (LCM) of the selected denominations.
    • Use the inclusion-exclusion principle to calculate the number of values up to mx that can be formed using these sums.
      • If the number of selected coins in the subset is odd, add the floor division of mx by their LCM (cnt += mx // v).
      • If even, subtract it (cnt -= mx // v).

  3. Inclusion-Exclusion Principle:

    • The principle is used to accurately account for all combinations possible with the given coin denominations, ensuring that overlaps are handled correctly.
    • For example, with denominations a and b, the formula becomes: 
      floor(mx/a) + floor(mx/b) - floor(mx/lcm(a, b))

  4. Executing Binary Search:

    • The search proceeds by calculating a midpoint, mid, and evaluating if check(mid) is true.
    • If true, adjust the upper bound (r = mid). If false, adjust the lower bound (l = mid + 1).
    • This continues iteratively to hone in on the smallest x where the inclusion-exclusion count is at least k.

Through the above steps, the solution effectively balances enumeration with computational efficiency, ensuring correct results within feasible runtime limits despite the complexity introduced by the inclusion-exclusion process in handling different coin subsets.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a simple example.

Suppose you have coins = [1, 2, 5] and k = 5. We want to find the 5th smallest amount that can be formed using these coins without combining different denominations.

Step 1: Binary Search Setup

  • We initialize the binary search range with l = 1 and r = 10^11.

Step 2: Applying Binary Search

  • Calculate mid = (l + r) // 2.

Step 3: Use the check() Function

  • This function counts how many valid amounts can be made using the coins up to mid.

    • For each non-empty subset of coins, calculate the Least Common Multiple (LCM).

      • Example subsets for [1, 2, 5]:
        • {1}: LCM = 1
        • {2}: LCM = 2
        • {5}: LCM = 5
        • {1, 2}: LCM = 2
        • {1, 5}: LCM = 5
        • {2, 5}: LCM = 10
        • {1, 2, 5}: LCM = 10

    • Use inclusion-exclusion to count numbers up to mid:

      • For odd-sized subsets, add floor(mid / LCM).
      • For even-sized subsets, subtract floor(mid / LCM).

Step 4: Adjust Search Range

  • If the count from check(mid) is at least k, move the upper bound r to mid.
  • Otherwise, move the lower bound l to mid + 1.

Continue Binary Search

  • Continue the binary search until l equals r. The final value of l is the smallest amount for which the count reaches k.

Example Conclusion

  • Through the binary search iterations, you are checking the count of valid amounts for different mid values.
  • Eventually, you find that l = 5 is the 5th smallest amount because the previous counts were not sufficient before reaching this number, confirming the methodology's precision in finding the correct result efficiently.

Solution Implementation

1from typing import List
2from math import gcd
3from bisect import bisect_left
4
5def lcm(a: int, b: int) -> int:
6    """Calculate the Least Common Multiple of two numbers."""
7    return abs(a * b) // gcd(a, b)
8
9class Solution:
10    def findKthSmallest(self, coins: List[int], k: int) -> int:
11        def check(max_value: int) -> bool:
12            """Check if there are at least k numbers less than or equal to max_value composed by LCM of subsets."""
13            cnt = 0
14            num_subsets = 1 << len(coins)  # Total number of subsets
15            for subset_index in range(1, num_subsets):
16                subset_lcm = 1
17                for coin_index, coin in enumerate(coins):
18                    if subset_index >> coin_index & 1:
19                        subset_lcm = lcm(subset_lcm, coin)
20                        if subset_lcm > max_value:
21                            break
22                num_elements_in_subset = bin(subset_index).count('1')
23                if num_elements_in_subset % 2 == 1:
24                    cnt += max_value // subset_lcm
25                else:
26                    cnt -= max_value // subset_lcm
27            return cnt >= k
28
29        # Use binary search to find the k-th smallest number
30        return bisect_left(range(10**11), True, key=check)
31
1class Solution {
2    private int[] coins;
3    private int k;
4
5    public long findKthSmallest(int[] coins, int k) {
6        this.coins = coins;
7        this.k = k;
8
9        long left = 1, right = (long) 1e11;
10      
11        // Use binary search to find the kth smallest number
12        while (left < right) {
13            long mid = (left + right) / 2;
14          
15            // Check if the mid value can be the kth smallest number
16            if (check(mid)) {
17                right = mid; // If true, try smaller mid
18            } else {
19                left = mid + 1; // If false, try larger mid
20            }
21        }
22        return left;
23    }
24
25    // Method to check if there are at least k numbers <= mx that
26    // can be formed using LCM of any subset of given coins
27    private boolean check(long mx) {
28        long count = 0;
29        int n = coins.length;
30
31        // Iterate over all non-empty subsets of coins
32        for (int i = 1; i < 1 << n; ++i) {
33            long lcmValue = 1;
34
35            // Calculate the LCM for the current subset
36            for (int j = 0; j < n; ++j) {
37                if ((i >> j & 1) == 1) {
38                    lcmValue = lcm(lcmValue, coins[j]);
39
40                    // If LCM exceeds mx, stop calculating further
41                    if (lcmValue > mx) {
42                        break;
43                    }
44                }
45            }
46
47            int subsetSize = Integer.bitCount(i);
48
49            // Use inclusion-exclusion principle to calculate count
50            if (subsetSize % 2 == 1) {
51                count += mx / lcmValue;
52            } else {
53                count -= mx / lcmValue;
54            }
55        }
56        return count >= k;
57    }
58
59    // Helper method to calculate LCM of two numbers
60    private long lcm(long a, long b) {
61        return a * b / gcd(a, b);
62    }
63
64    // Helper method to calculate GCD of two numbers
65    private long gcd(long a, long b) {
66        return b == 0 ? a : gcd(b, a % b);
67    }
68}
69
1#include <vector>
2#include <algorithm>
3#include <numeric> // for std::lcm
4using namespace std;
5
6class Solution {
7public:
8    // This function finds the k-th smallest number that can be formed
9    // as a multiple of the least common multiples (LCM) of subsets of the 'coins.'
10    long long findKthSmallest(vector<int>& coins, int k) {
11        using ll = long long; // Define a type alias for long long.
12        ll left = 1, right = 1e11; // Define the search range for the k-th smallest number.
13        int n = coins.size(); // Get the number of coins.
14
15        // Lambda function to check if a given number 'maxValue' is enough to form k multiples.
16        auto check = [&](ll maxValue) {
17            ll count = 0; // Initialize a count to store the number of valid multiples.
18            // Iterate through each non-empty subset of 'coins.'
19            for (int i = 1; i < (1 << n); ++i) {
20                ll lcmValue = 1; // Initialize the LCM value for this subset.
21                for (int j = 0; j < n; ++j) {
22                    // Check if the j-th coin is in the current subset.
23                    if (i & (1 << j)) {
24                        // Calculate the LCM of the current subset.
25                        lcmValue = lcm(lcmValue, (ll)coins[j]);
26                        // If LCM exceeds maxValue, break out of the loop.
27                        if (lcmValue > maxValue) {
28                            break;
29                        }
30                    }
31                }
32                // Use inclusion-exclusion principle to update the count.
33                int subsetSize = __builtin_popcount(i); // Count the number of elements in subset.
34                if (subsetSize & 1) { // If subset size is odd, add the number of multiples.
35                    count += maxValue / lcmValue;
36                } else { // If subset size is even, subtract the number of multiples.
37                    count -= maxValue / lcmValue;
38                }
39            }
40            // Return true if we have at least k multiples, otherwise false.
41            return count >= k;
42        };
43
44        // Apply binary search to find the k-th smallest number.
45        while (left < right) {
46            ll mid = (left + right) / 2;
47            if (check(mid)) {
48                right = mid; // Mid is a potential solution, search in the lower half.
49            } else {
50                left = mid + 1; // Mid is not sufficient, search in the upper half.
51            }
52        }
53        // Return the left boundary, which is the k-th smallest number.
54        return left;
55    }
56};
57
1// Function to find the k-th smallest number that can be evenly divided by any subset of the given coin values
2function findKthSmallest(coins: number[], k: number): number {
3    // Initialize the search range for binary search
4    let [l, r] = [1n, BigInt(1e11)]; // Use big integers for large values
5    const n = coins.length;
6
7    // Helper function to check whether there are at least k numbers <= mx
8    const check = (mx: bigint): boolean => {
9        let count = 0n;
10        // Go through all subsets of coins
11        for (let i = 1; i < 1 << n; ++i) {
12            let value = 1n;
13            // Calculate the least common multiple (LCM) of coins in the current subset
14            for (let j = 0; j < n; ++j) {
15                if ((i >> j) & 1) {
16                    value = lcm(value, BigInt(coins[j]));
17                    // If LCM exceeds current mx, break out
18                    if (value > mx) {
19                        break;
20                    }
21                }
22            }
23            // Include or exclude counts based on the number of bits set (inclusion-exclusion principle)
24            const m = bitCount(i);
25            if (m & 1) {
26                count += mx / value;
27            } else {
28                count -= mx / value;
29            }
30        }
31        return count >= BigInt(k);
32    };
33
34    // Perform binary search to find the k-th smallest number
35    while (l < r) {
36        const mid = (l + r) >> 1n; // Calculate mid-point
37        if (check(mid)) {
38            r = mid; // Narrow search to left half
39        } else {
40            l = mid + 1n; // Narrow search to right half
41        }
42    }
43    return Number(l); // Return the k-th smallest number
44}
45
46// Helper function to calculate the greatest common divisor (GCD) of two numbers
47function gcd(a: bigint, b: bigint): bigint {
48    return b === 0n ? a : gcd(b, a % b);
49}
50
51// Helper function to calculate the least common multiple (LCM) of two numbers
52function lcm(a: bigint, b: bigint): bigint {
53    return (a * b) / gcd(a, b);
54}
55
56// Helper function to count the number of 1-bits in the binary representation of a number
57function bitCount(i: number): number {
58    i = i - ((i >>> 1) & 0x55555555);
59    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
60    i = (i + (i >>> 4)) & 0x0f0f0f0f;
61    i = i + (i >>> 8);
62    i = i + (i >>> 16);
63    return i & 0x3f;
64}
65

Time and Space Complexity

The code uses a combination of bit manipulation and the inclusion-exclusion principle to determine the k-th smallest number that can be formed as a least common multiple (LCM) of subsets of coins. Analyze the time complexity step-by-step:

  1. Iterating through subsets: The loop for i in range(1, 1 << len(coins)): iterates over all possible subsets of coins except the empty subset. This results in O(2^n) iterations, where n is len(coins).

  2. Computing LCMs: Inside the subset loop, v = lcm(v, x) is calculated for each combination, which takes O(n) time. The break condition when v > mx can potentially reduce the overall number of computations, although it doesn't affect asymptotic complexity.

  3. Binary Search: The call bisect_left(range(10**11), True, key=check) performs a binary search over a range, typically operating in O(\log R) time. Here R is a proxy for k * M, where M is the maximum element in coins.

Combining these components, the overall time complexity is O(n \times 2^n \times \log (k \times M)).

Space Complexity

The space complexity is primarily dictated by auxiliary storage used in variables. Here, only a constant amount of space is used for variables and counters, outside of storing coins. Thus, the space complexity is O(1) relative to the computation performed (ignores input holding space).

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Binary Search Speedrun

Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More