Kth smallest amount with single denomination combination

Array Math Binary Search Bit Manipulation Combinatorics Number Theory

20.0% acceptance

Feb 23, 2026

252

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_kth_smallest(coins: Vec<i32>, k: i32) -> i64 {
    let n = coins.len();
    let k = k as i64;

    // Count multiples <= x using inclusion-exclusion on LCM of subsets
    let count = |x: i64| -> i64 {
      let mut total: i64 = 0;
      for mask in 1u32..(1 << n) {
        let mut lcm_val: i64 = 1;
        let mut bits = 0u32;
        for j in 0..n {
          if mask & (1 << j) != 0 {
            bits += 1;
            let g = gcd(lcm_val, coins[j] as i64);
            lcm_val = lcm_val / g * coins[j] as i64;
            if lcm_val > x {
              lcm_val = x + 1; // overflow guard
              break;
            }
          }
        }
        let contrib = x / lcm_val;
        if bits % 2 == 1 {
          total += contrib;
        } else {
          total -= contrib;
        }
      }
      total
    };

    // Binary search for the smallest x where count(x) >= k
    let mut lo: i64 = 1;
    let mut hi: i64 = k * *coins.iter().min().unwrap() as i64;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if count(mid) >= k {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}

fn gcd(a: i64, b: i64) -> i64 {
  if b == 0 { a } else { gcd(b, a % b) }
}