Maximum number that sum of the prices is less than or equal to k

Math Binary Search Dynamic Programming Bit Manipulation

38.5% acceptance

Feb 25, 2026

342

131

You are given an integer k and an integer x. The price of a number num is calculated by the count of set bits at positions x, 2x, 3x, etc., in its binary representation, starting from the least significant bit. The following table contains examples of how price is calculated. The accumulated price of num is the total price of numbers from 1 to num. num is considered cheap if its accumulated price is less than or equal to k. Return the greatest cheap number.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn find_maximum_number(k: i64, x: i32) -> i64 {
    let x = x as u32;
    let price = |num: i64| -> i64 {
      // Count set bits at positions x, 2x, 3x, ... (1-indexed from LSB) in 1..=num
      let mut total = 0i64;
      let mut bit = x;
      while bit <= 50 {
        // Count numbers in [1, num] with bit `bit` set (1-indexed, so bit position = bit-1 in 0-indexed)
        let pos = bit - 1;
        let cycle = 1i64 << (pos + 1);
        let half = 1i64 << pos;
        total += (num / cycle) * half + (num % cycle - half + 1).max(0);
        bit += x;
      }
      total
    };
    let mut lo = 1i64;
    let mut hi = (1i64 << 50) - 1;
    while lo < hi {
      let mid = lo + (hi - lo + 1) / 2;
      if price(mid) <= k { lo = mid; } else { hi = mid - 1; }
    }
    lo
  }
}