# Maximum Number That Sum of the Prices Is Less Than or Equal to K **Difficulty:** MEDIUM [External](https://leetcode.com/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k) Canonical: https://scaleengineer.com/dsa/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation) **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) --- ## Problem 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. | x | num | Binary Representation | Price | | - | --- | ---------------------- | ----- | | 1 | 13 | 00000**1** **1**0**1** | 3 | | 2 | 13 | 00000**1**101 | 1 | | 2 | 233 | 0**1**1**1**0**1**001 | 3 | | 3 | 13 | 000001**1**01 | 1 | | 3 | 362 | **1**01**1**01010 | 2 | 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. **Example 1:** **Input:** k = 9, x = 1 **Output:** 6 **Explanation:** As shown in the table below, `6` is the greatest cheap number. | x | num | Binary Representation | Price | Accumulated Price | | - | --- | --------------------- | ----- | ----------------- | | 1 | 1 | 00**1** | 1 | 1 | | 1 | 2 | 0**1**0 | 1 | 2 | | 1 | 3 | 0**1** **1** | 2 | 4 | | 1 | 4 | **1**00 | 1 | 5 | | 1 | 5 | **1**0**1** | 2 | 7 | | 1 | 6 | **1** **1**0 | 2 | 9 | | 1 | 7 | **1** **1** **1** | 3 | 12 | **Example 2:** **Input:** k = 7, x = 2 **Output:** 9 **Explanation:** As shown in the table below, `9` is the greatest cheap number. | x | num | Binary Representation | Price | Accumulated Price | | - | --- | --------------------- | ----- | ----------------- | | 2 | 1 | 0001 | 0 | 0 | | 2 | 2 | 00**1**0 | 1 | 1 | | 2 | 3 | 00**1**1 | 1 | 2 | | 2 | 4 | 0100 | 0 | 2 | | 2 | 5 | 0101 | 0 | 2 | | 2 | 6 | 01**1**0 | 1 | 3 | | 2 | 7 | 01**1**1 | 1 | 4 | | 2 | 8 | **1**000 | 1 | 5 | | 2 | 9 | **1**001 | 1 | 6 | | 2 | 10 | **1**0**1**0 | 2 | 8 | **Constraints:** * `1 <= k <= 1015` * `1 <= x <= 8` # Approaches ## Brute Force Iteration This is the most straightforward approach. We can iterate through each number `num` starting from 1. For each `num`, we calculate its price and add it to a running total, the `accumulated_price`. We continue this process as long as the `accumulated_price` does not exceed `k`. The last number `num` for which this condition holds is our answer. **Time:** O(N * (log N / x)), where N is the final answer. Since N can be very large, this is too slow. · **Space:** O(1) - We only use a few variables to store the current number and the accumulated price. **Pros:** Very simple logic, easy to understand and implement. **Cons:** Extremely inefficient. The number of iterations is equal to the answer, which can be very large (`~10^15`).; Will result in a Time Limit Exceeded (TLE) error for the given constraints. ### Explanation We initialize `accumulatedPrice` to 0 and loop `num` from 1 upwards. In each step, we calculate the price of the current `num`. The price is the number of set bits at positions that are multiples of `x` (i.e., `x`, `2x`, `3x`, ...). We add this price to `accumulatedPrice`. If `accumulatedPrice` becomes greater than `k`, it means the current `num` makes the total price too high. Therefore, the previous number, `num - 1`, is the maximum cheap number. This method is too slow for the given constraints on `k` because the answer `num` can be very large, making the loop run too many times. ```java class Solution { private long getPrice(long num, int x) { long price = 0; for (int i = x; i <= 63; i += x) { if ((num & (1L << (i - 1))) != 0) { price++; } } return price; } public long findMaximumNumber(long k, int x) { long accumulatedPrice = 0; long num = 0; while (true) { num++; long priceOfNum = getPrice(num, x); if (accumulatedPrice > k - priceOfNum) { return num - 1; } accumulatedPrice += priceOfNum; } } } ``` ### Algorithm - 1. Initialize `accumulatedPrice = 0L` and `num = 0L`. - 2. Start a loop that increments `num` by 1 in each iteration. - 3. Inside the loop, calculate `priceOfNum`: - a. Initialize `priceOfNum = 0`. - b. Iterate through bit positions `pos = x, 2*x, 3*x, ...` up to a reasonable limit (e.g., 63, for `long`). - c. Check if the `pos`-th bit of `num` is set using the bitwise AND operation `(num & (1L << (pos - 1))) != 0`. - d. If it is set, increment `priceOfNum`. - 4. Check if adding `priceOfNum` to `accumulatedPrice` would exceed `k`. This is to prevent overflow and unnecessary calculations: `if (accumulatedPrice > k - priceOfNum)`. - 5. If it exceeds `k`, then `num - 1` is the answer. Return `num - 1`. - 6. Otherwise, update `accumulatedPrice += priceOfNum`. ## Binary Search with Naive Accumulated Price Calculation The problem asks for the "greatest" cheap number. The function `accumulated_price(num)` is monotonically increasing with `num`. This allows us to use binary search on the answer `num`. For each `mid` value in our binary search, we check if `accumulated_price(mid) <= k`. **Time:** O(S * log(S) * log(S)), where S is the size of the search space. This is too slow. · **Space:** O(1) **Pros:** Correctly identifies the monotonic property of the problem, leading to a binary search structure. **Cons:** The check function is very slow. The complexity of `isCheap(num, ...)` is `O(num * log(num))`, making the overall approach time-out. ### Explanation We can binary search for the answer `num` in a large range, for example, from `1` to `2 * 10^16`. For each `mid` value, we need to check if it's a "cheap" number. In this approach, we calculate `accumulated_price(mid)` by iterating from `i = 1` to `mid`, calculating the price of each `i`, and summing them up. If `accumulated_price(mid) <= k`, it means `mid` could be our answer, and we search in the right half (`low = mid + 1`). Otherwise, `mid` is too large, so we search in the left half (`high = mid - 1`). While this approach correctly uses binary search, the check function itself is too slow. ```java class Solution { private long getPrice(long num, int x) { long price = 0; for (int i = x; i <= 63; i += x) { if ((num & (1L << (i - 1))) != 0) { price++; } } return price; } private boolean isCheap(long num, long k, int x) { long accumulatedPrice = 0; for (long i = 1; i <= num; i++) { accumulatedPrice += getPrice(i, x); if (accumulatedPrice > k) { return false; } } return true; } public long findMaximumNumber(long k, int x) { long low = 1, high = 20000000000000000L; // A sufficiently large upper bound long ans = 0; while (low <= high) { long mid = low + (high - low) / 2; if (mid == 0) { low = 1; continue; } if (isCheap(mid, k, x)) { ans = mid; low = mid + 1; } else { high = mid - 1; } } return ans; } } ``` ### Algorithm - 1. Define a search range for the answer, `low = 1`, `high = 2 * 10^16` (a safe upper bound). Initialize `ans = 0`. - 2. While `low <= high`: - a. Calculate `mid = low + (high - low) / 2`. - b. Call a helper function `isCheap(mid, k, x)` to check if `mid` is a cheap number. - c. If `isCheap` returns true: - i. `mid` is a potential answer. Store it: `ans = mid`. - ii. Try for a larger number: `low = mid + 1`. - d. If `isCheap` returns false: - i. `mid` is too large. Search in the lower half: `high = mid - 1`. - 3. Return `ans`. - **`isCheap(num, k, x)` function:** - a. Initialize `totalPrice = 0`. - b. Loop `i` from 1 to `num`. - c. For each `i`, calculate its price by checking bits at positions `x, 2x, ...`. - d. Add the price of `i` to `totalPrice`. - e. If at any point `totalPrice > k`, return `false` immediately. - f. If the loop completes, return `true`. ## Binary Search with Combinatorial Price Calculation This is the optimal approach. It builds upon the binary search idea but uses a much faster way to calculate the accumulated price. Instead of summing prices one by one, we calculate the total contribution of each relevant bit position across all numbers from 1 to `num`. **Time:** O((log S / x) * log S), where S is the size of the search space. Given S is up to `~10^16`, `log S` is ~64. The complexity is effectively `O((1/x) * (log k)^2)`, which is very fast. · **Space:** O(1) **Pros:** Highly efficient and solves the problem within the given time constraints.; The check function is very fast, with a complexity independent of the input number `num`. **Cons:** The logic for calculating the accumulated price is more complex and less intuitive than the brute-force methods. ### Explanation The core idea is to change the order of summation for `accumulated_price(num)`. Instead of `sum over numbers (sum over bits)`, we do `sum over bits (sum over numbers)`. The inner sum becomes counting how many numbers from 1 to `num` have a specific bit set. We can write an efficient helper function, `countSetBitsAtPos(num, pos)`, to calculate this count. The bits at any position `pos` follow a periodic pattern: `2^(pos-1)` zeros, then `2^(pos-1)` ones, repeating. We can use this pattern to calculate the count in `O(1)` time using division and modulo operations. The `accumulated_price(num)` function then loops through the relevant bit positions (`x, 2x, 3x, ...`) and sums up the results from `countSetBitsAtPos`. This calculation is very fast, taking `O(log(num))` time. With this efficient check, the binary search becomes feasible. ```java class Solution { // Calculates the total price for all numbers from 1 to num. private long getAccumulatedPrice(long num, int x) { long totalPrice = 0; // Iterate through each bit position that contributes to the price. // Positions are 1-indexed. for (int pos = x; pos <= 63; pos += x) { // Calculate how many numbers from 1 to num have the pos-th bit set. long period = 1L << pos; long halfPeriod = period / 2; // Count numbers in the range [0, num], which is num + 1 numbers. long numAndZero = num + 1; // Number of full periods. long numPeriods = numAndZero / period; // Each full period has halfPeriod numbers with the pos-th bit set. long count = numPeriods * halfPeriod; // Count in the remaining part of the last, incomplete period. long remainder = numAndZero % period; count += Math.max(0L, remainder - halfPeriod); totalPrice += count; } return totalPrice; } public long findMaximumNumber(long k, int x) { long low = 1; long high = 20000000000000000L; // A safe upper bound long ans = 0; while (low <= high) { long mid = low + (high - low) / 2; if (mid == 0) { low = 1; continue; } long accumulatedPrice = getAccumulatedPrice(mid, x); if (accumulatedPrice <= k) { // mid is a potential answer, try for a larger one. ans = mid; low = mid + 1; } else { // mid is too large, search in the lower half. high = mid - 1; } } return ans; } } ``` ### Algorithm - 1. The main structure is a binary search on the answer `num` in a range like `[1, 2 * 10^16]`. - 2. In each step of the binary search, for a given `mid`, we calculate `accumulated_price(mid)` using an efficient helper function. - 3. **`getAccumulatedPrice(num, x)` function:** - a. Initialize `totalPrice = 0`. - b. Loop through bit positions `pos = x, 2*x, 3*x, ...` up to 63. - c. For each `pos`, calculate the number of integers from 1 to `num` that have the `pos`-th bit set. - i. The pattern of the `pos`-th bit has a full cycle length of `period = 1L << pos`. - ii. The number of full periods in `num+1` numbers (from 0 to `num`) is `num_periods = (num + 1) / period`. - iii. Each full period contributes `period / 2` set bits. - iv. The remaining numbers are `remainder = (num + 1) % period`. - v. The contribution from the remainder is `max(0, remainder - (period / 2))`. - vi. The total count for position `pos` is the sum of contributions from full periods and the remainder. - d. Add this count to `totalPrice`. - 4. After the loop, return `totalPrice`. - 5. Back in the binary search, if `getAccumulatedPrice(mid, x) <= k`, we search for a larger answer (`ans = mid`, `low = mid + 1`). Otherwise, we search for a smaller one (`high = mid - 1`). # Solutions ### Java ```java class Solution { private int x ; private long num ; private Long [][] f ; public long findMaximumNumber ( long k , int x ) { this . x = x ; long l = 1 , r = ( long ) 1 e17 ; while ( l < r ) { long mid = ( l + r + 1 ) >>> 1 ; num = mid ; f = new Long [ 65 ][ 65 ]; int pos = 64 - Long . numberOfLeadingZeros ( mid ); if ( dfs ( pos , 0 , true ) <= k ) { l = mid ; } else { r = mid - 1 ; } } return l ; } private long dfs ( int pos , int cnt , boolean limit ) { if ( pos == 0 ) { return cnt ; } if (! limit && f [ pos ][ cnt ] != null ) { return f [ pos ][ cnt ]; } long ans = 0 ; int up = limit ? ( int ) ( num >> ( pos - 1 ) & 1 ) : 1 ; for ( int i = 0 ; i <= up ; ++ i ) { ans += dfs ( pos - 1 , cnt + ( i == 1 && pos % x == 0 ? 1 : 0 ), limit && i == up ); } if (! limit ) { f [ pos ][ cnt ] = ans ; } return ans ; } } ``` ### CPP ```cpp class Solution { public: long long findMaximumNumber(long long k, int x) { using ll = long long; ll l = 1, r = 1e17; ll num = 0; ll f[65][65]; function dfs = [&](int pos, int cnt, bool limit) -> ll { if (pos == 0) { return cnt; } if (!limit && f[pos][cnt] != -1) { return f[pos][cnt]; } int up = limit ? num >> (pos - 1) & 1 : 1; ll ans = 0; for (int i = 0; i <= up; ++i) { ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0), limit && i == up); } if (!limit) { f[pos][cnt] = ans; } return ans; }; while (l < r) { ll mid = (l + r + 1) >> 1; num = mid; memset(f, -1, sizeof(f)); int pos = 64 - __builtin_clzll(mid); if (dfs(pos, 0, true) <= k) { l = mid; } else { r = mid - 1; } } return l; } }; ``` ### Python ```python class Solution: def findMaximumNumber(self, k: int, x: int) -> int: @ cache def dfs(pos, limit, cnt): if pos == 0: return cnt ans = 0 up = (self . num >> (pos - 1) & 1) if limit else 1 for i in range(up + 1): ans += dfs(pos - 1, limit and i == up, cnt + (i == 1 and pos % x == 0)) return ans l, r = 1, 10 ** 18 while l < r: mid = (l + r + 1) >> 1 self . num = mid v = dfs(mid . bit_length(), True, 0) dfs . cache_clear() if v <= k: l = mid else: r = mid - 1 return l ```