3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
Problem Description
In this problem, we're given two integers, k and x. Our goal is to find the maximum integer num such that the sum of the "prices" of all integers from 1 to num does not exceed k. The term "price" of a number is defined based on its binary representation. Specifically, for a 1-indexed binary representation s of a number num, the price is the count of indices i such that i % x == 0 and the i-th bit of s is set (meaning it is a '1' bit).
To recap the rules regarding the price calculation:
- We consider the binary representation on a 1-based index system.
- A set bit is a bit with the value '1'.
- The price of a number is the count of set bits at positions that are multiples of
x.
As an example, if x is 2, then we are only interested in the set bits at even positions within the binary representation of the number. The task is to find the largest number whose cumulative price from 1 up to that number is less than or equal to k.
Intuition
This problem falls into the category of binary search problems because we're trying to find the largest number num constrained by a specific condition (the cumulative price being less than or equal to k). The key intuition here is that if a certain 'num' has a cumulative price more than k, then all numbers greater than 'num' will surely have a cumulative price more than k, while if 'num' is within the budget of k, all numbers less than num are also within the budget. This makes the condition monotonic, which is the basic property allowing us to use binary search.
To implement this approach, we define the binary search boundaries (l and r) and keep adjusting these boundaries based on whether the midpoint of the current range (mid) has a cumulative price within our budget of k. The dfs function is used to recursively compute the cumulative price and uses memoization to optimize the calculation by caching intermediate results. The binary search continues until we pinpoint the largest num that meets the condition.
In essence, our solution involves iteratively narrowing down our search space using binary search while simultaneously using a depth-first search function that computes whether a given number falls within the budget constraint provided by k.
Learn more about Binary Search and Dynamic Programming patterns.
How does quick sort divide the problem into subproblems?
Solution Approach
The solution involves a combination of binary search and depth-first search (DFS) with memoization to efficiently calculate the sum of prices for the numbers ranging from 1 to a candidate number.
Binary Search:
The binary search operates in the range of [1, 10^18]. The high range is provided to ensure that we do not miss any potential number. The while loop in the binary search keeps narrowing the search space until the left (l) and right (r) pointers converge, which will give us the largest possible number with a cumulative price within the budget k.
Within each iteration of the binary search, we compute the mid-point (mid) and set self.num = mid to represent the current maximum number under consideration. We then calculate the cumulative price for all numbers up to mid using the dfs function. If the calculated price v is within the budget (i.e., v <= k), we move the lower bound of the search range l to mid. Otherwise, we adjust the upper bound r to mid - 1.
DFS with Memoization:
The dfs function is a recursive function that calculates the price of the binary representation of a number from position pos to the least significant bit. The function takes as parameters the position pos, a boolean limit which indicates if we are at the upper bound of the current number being evaluated, and cnt which keeps track of the number of set bits that are at positions which are multiples of x.
The base case for the recursion occurs when pos == 0, where we return the count of prices.
For each recursive call, we determine the potential value of the current bit by checking if we are limited by the upper bound. If we are at the limit (limit is True), we can only place a '1' in this position if the corresponding bit in self.num is also '1', otherwise we can place both '0' and '1'.
Finally, we use @cache from the functools module to memoize the results of the dfs function to avoid recomputing prices for the same input arguments. The cache is cleared after each calculation with dfs.cache_clear() to prepare for the next iteration with a new mid-point in the binary search.
The combination of binary search and memoized DFS ensures that we minimize the number of redundant calculations and efficiently home in on the largest number that satisfies the given constraints.
Depth first search can be used to find whether two components in a graph are connected.
Example Walkthrough
Let's go through a small example to illustrate the solution approach using the combination of binary search and DFS with memoization. Consider k = 5 and x = 2, which means we want to find the maximum number num such that the sum of the prices (based on every second bit set in their binary representations) of all integers from 1 to num does not exceed 5.
We'll start our binary search with l = 1 and r = 10^18 as our initial boundaries.
During our first iteration:
- We calculate
midby averaginglandr. For simplicity, let's suppose that our firstmidis4. - Now we use the DFS function to determine the cumulative price for all numbers up to
4. - In binary, numbers from
1to4are1,10,11, and100. - The prices are based on set bits at even positions. So, the price of
1is0(no second bit), the price of2 (10)is1, the price of3 (11)is1(only considering the second bit), and the price of4 (100)is0. - Thus, the cumulative price for numbers
1to4is0 + 1 + 1 + 0 = 2, which is less thank=5. - Since
2is within our budget, we can safely moveltomid, to start checking bigger numbers.
Now, let's suppose l is updated to 4 and repeat the process:
- Let's say our new
midis8. - We again calculate the cumulative price for numbers
1to8. - The prices for numbers
5to8would be similarly calculated and the new total would include the sums from the previous step (1to4). - If this sum stays within
k=5, we continue movinglup. Otherwise, we would moverdown tomid - 1.
Let's assume that our cumulative price went over the budget when we checked up to 8, then we would set r to 7 and continue our binary search.
This binary search and DFS process continues, narrowing down the range using the cumulative price, until l and r converge, which would occur when l cannot move to the right anymore without going over the budget k. The final l at that point would be our desired largest num.
Throughout this process, DFS computes prices and uses memoization to remember price calculations for particular bit positions, limits, and counts to avoid redundant computations. This memoization is critical to ensure an efficient binary search, especially considering we're dealing with potentially huge numbers up to 10^18. After each full calculation of a cumulative price for a mid point, dfs.cache_clear() is called to reset the memoization cache in preparation for the next iteration.
By the end, we find the largest possible num such that the cumulative price of all numbers from 1 to num is less than or equal to k, which will be our solution to the problem.
Solution Implementation
1from functools import lru_cache # Importing the required decorator for caching.
2
3# Define the Solution class.
4class Solution:
5 def findMaximumNumber(self, k: int, x: int) -> int:
6 # This internal function performs a depth-first search to calculate the count of values satisfying the condition.
7 # It utilizes dynamic programming with memoization to cache and reuse the results.
8 @lru_cache(None) # Using lru_cache to memoize the function results.
9 def dfs(position, is_limited, count_ones):
10 # If the position is 0, return the count of ones encountered.
11 if position == 0:
12 return count_ones
13 # Initialize the answer for the current state.
14 ans = 0
15 # Calculate the upper limit for the current bit position.
16 upper_limit = (self.number >> (position - 1) & 1) if is_limited else 1
17 # Iterate over the possible values for the current bit (0 or 1).
18 for i in range(upper_limit + 1):
19 # Update the answer by recursively calling dfs function for the next position.
20 ans += dfs(position - 1, is_limited and i == upper_limit, count_ones + (i == 1 and position % x == 0))
21 # Return the answer calculated for the current state.
22 return ans
23
24 # Initialize the search range.
25 left, right = 1, 10**18
26 # Perform a binary search to find the maximum number satisfying the condition.
27 while left < right:
28 mid = (left + right + 1) >> 1
29 self.number = mid
30 # Calculate the value by calling the dfs function starting from the most significant bit.
31 value = dfs(mid.bit_length(), True, 0)
32 # Clear the cache before the next iteration.
33 dfs.cache_clear()
34 # Narrow down the search range based on the value obtained from dfs.
35 if value <= k:
36 left = mid
37 else:
38 right = mid - 1
39 # Return the maximum number satisfying the condition.
40 return left
41
42# Note: The above code will only run in a Python 3 environment where the lru_cache decorator is available.
431class Solution {
2 private int numberOfBitsToCount;
3 private long targetNumber;
4 private Long[][] memoizationArray;
5
6 public long findMaximumNumber(long k, int x) {
7 this.numberOfBitsToCount = x;
8 long left = 1, right = (long) 1e17;
9
10 // Binary search loop to find the maximum number
11 // such that the count of bits at positions
12 // multiple of x is less than or equal to k.
13 while (left < right) {
14 long mid = (left + right + 1) >>> 1;
15 targetNumber = mid;
16
17 // Reset the memoization array for dynamic programming.
18 memoizationArray = new Long[65][65];
19
20 // Compute the position of the highest bit of the mid value.
21 int pos = 64 - Long.numberOfLeadingZeros(mid);
22
23 // Depth-first search to count the bits
24 if (computeBits(pos, 0, true) <= k) {
25 left = mid;
26 } else {
27 right = mid - 1;
28 }
29 }
30 return left;
31 }
32
33 private long computeBits(int pos, int count, boolean limit) {
34 // Base case: if we've reached the least significant bit.
35 if (pos == 0) {
36 return count;
37 }
38
39 // Use memoization to save previously calculated results for efficiency.
40 if (!limit && memoizationArray[pos][count] != null) {
41 return memoizationArray[pos][count];
42 }
43
44 long total = 0;
45 int upperLimit = limit ? (int) (targetNumber >> (pos - 1) & 1) : 1;
46
47 // Iterate over the possible bit values (0 or 1)
48 for (int i = 0; i <= upperLimit; ++i) {
49 total += computeBits(pos - 1, count + (i == 1 && pos % numberOfBitsToCount == 0 ? 1 : 0), limit && i == upperLimit);
50 }
51
52 // Cache the computed result for future queries.
53 if (!limit) {
54 memoizationArray[pos][count] = total;
55 }
56 return total;
57 }
58}
591class Solution {
2public:
3 using ll = long long;
4
5 // This function finds the maximum number with a specific number of bits set at positions
6 // that are multiples of x and that are less than or equal to a given limit k.
7 long long findMaximumNumber(long long k, int x) {
8 ll left = 1; // Represents the start of our search range.
9 ll right = 1e17; // An upper bound for our search. Could be any sufficiently large number.
10 ll number = 0; // Will hold the current number we're evaluating.
11
12 // A memoization table to store intermediate results for the dynamic programming approach.
13 ll memo[65][65];
14
15 // A depth-first search function that returns the number of bits set at
16 // positions which are multiples of x in the binary representation of the number.
17 auto dfs = [&](int pos, int count, bool limit) -> ll {
18 // Base case: if there are no more positions to set, just return the count.
19 if (pos == 0) {
20 return count;
21 }
22 // If we are not at the limit and the result is already computed, return it.
23 if (!limit && memo[pos][count] != -1) {
24 return memo[pos][count];
25 }
26 // Calculate the upper bound on the bit value based on whether the limit is true.
27 int upperBound = limit ? (number >> (pos - 1)) & 1 : 1;
28 ll ans = 0;
29 // Recur for both setting the current bit and not setting it.
30 for (int i = 0; i <= upperBound; ++i) {
31 ans += dfs(pos - 1, count + (i == 1 && pos % x == 0), limit && i == upperBound);
32 }
33 // Only cache the result if we're not at the limit.
34 if (!limit) {
35 memo[pos][count] = ans;
36 }
37 return ans;
38 };
39
40 // Binary search to find the maximum number that satisfies the condition.
41 while (left < right) {
42 ll mid = (left + right + 1) >> 1; // Calculate the middle of the current range.
43 number = mid; // Set the current number to mid.
44 memset(memo, -1, sizeof(memo)); // Reset the memoization table.
45 int position = 64 - __builtin_clzll(mid); // Get the highest bit position.
46 // Use the dfs traversal result to decide whether to increase or decrease the range.
47 if (dfs(position, 0, true) <= k) {
48 left = mid;
49 } else {
50 right = mid - 1;
51 }
52 }
53
54 // The final left boundary is the sought maximum number.
55 return left;
56 }
57};
581type ll = bigint; // Using bigint as an equivalent of long long in TypeScript.
2
3// A memoization table to store intermediate results for the dynamic programming approach.
4const memo: ll[][] = Array.from({ length: 65 }, () => Array(65).fill(-1n));
5
6// A depth-first search function that returns the number of bits set at
7// positions which are multiples of x in the binary representation of the number.
8const dfs = (pos: number, count: number, limit: boolean, x: number, number: ll): ll => {
9 // Base case: if there are no more positions to set, return the count.
10 if (pos === 0) {
11 return BigInt(count);
12 }
13 // If we are not at the limit and the result is already computed, return it.
14 if (!limit && memo[pos][count] !== -1n) {
15 return memo[pos][count];
16 }
17 // Calculate the upper bound on the bit value based on whether the limit is true.
18 const upperBound = limit ? (number >> BigInt(pos - 1)) & 1n : 1n;
19 let ans: ll = 0n;
20 // Recur for both setting the current bit and not setting it.
21 for (let i = 0n; i <= upperBound; i++) {
22 ans += dfs(pos - 1, count + (i === 1n && pos % x === 0 ? 1 : 0), limit && i === upperBound, x, number);
23 }
24 // Only cache the result if we're not at the limit.
25 if (!limit) {
26 memo[pos][count] = ans;
27 }
28 return ans;
29};
30
31// This function finds the maximum number with a specific number of bits set at positions
32// that are multiples of x and that are less than or equal to a given limit k.
33const findMaximumNumber = (k: ll, x: number): ll => {
34 let left: ll = 1n; // Represents the start of our search range.
35 let right: ll = 1n << 64n; // An upper bound for our search range, using 2^64 as a sufficiently large number.
36 let number: ll = 0n; // Will hold the current number we're evaluating.
37
38 // Binary search to find the maximum number that satisfies the condition.
39 while (left < right) {
40 const mid: ll = (left + right + 1n) >> 1n; // Calculate the middle of the current range.
41 number = mid; // Set the current number to mid.
42 // Reset the memoization table.
43 for (let i = 0; i < 65; ++i) {
44 memo[i].fill(-1n);
45 }
46 const position = 64 - countLeadingZeroBits(mid); // Get the highest bit position using countLeadingZeroBits function.
47 // Use the dfs traversal result to decide whether to increase or decrease the search range.
48 if (dfs(position, 0, true, x, number) <= k) {
49 left = mid;
50 } else {
51 right = mid - 1n;
52 }
53 }
54
55 // The final left boundary is the sought maximum number.
56 return left;
57};
58
59// Function to count leading zero bits in a bigint number.
60const countLeadingZeroBits = (number: ll): number => {
61 let count = 0;
62 for (let i = 63; i >= 0; i--) {
63 if ((number >> BigInt(i)) & 1n) {
64 break;
65 }
66 count++;
67 }
68 return count;
69};
70The three-steps of Depth First Search are:
- Identify states;
- Draw the state-space tree;
- DFS on the state-space tree.
Time and Space Complexity
Time Complexity:
The given code is using a binary search and a recursive function with memoization (dfs) to solve a problem.
-
The binary search in the while loop runs until
lis less thanr. The search space is reduced by half in each iteration. This results in a time complexity ofO(log n)for the binary search, wherenis the maximum value of the target number. -
Inside the binary search, we call the recursive
dfsfunction, which is memoized to avoid redundant calculations. Thedfsadds a complexity that is a product of two aspects:-
The depth of the recursion, which is determined by the bit length of
mid. The bit length is proportional to the logarithm ofmid, so the max depth of the recursion isO(log mid). -
The branching factor at each call to
dfs, which is up to 2 due to the line:for i in range(up + 1). Therefore, in the worst-case scenario without memoization, the time complexity of thedfswould beO(2^(log mid)), which simplifies toO(mid).
-
However, with memoization, not all of these branches are explored due to the overlapping subproblems. The actual complexity of the memoized dfs is smaller, but hard to define precisely without more context on the distribution of calls and the impact of memoization. It would depend on the number of unique states, which are determined by (pos, limit, cnt) and these are tightly bound. A conservative estimate would be O(log mid * 2^x) as pos ranges from 1 to log mid and cnt ranges from 0 to x. This is a very rough estimate and could be significantly lower in practice.
Therefore, the combined time complexity of the binary search and the recursive dfs function is O(log n * log mid * 2^x).
Space Complexity:
-
The space complexity is determined mainly by the recursive stack and the cache used by the memoization decorator.
-
The recursion depth is at most the bit length of
mid, which isO(log mid). -
The cache will store results for each unique state
(pos, limit, cnt). The number of uniqueposvalues is at mostlog mid, and the number of uniquecntvalues is up tox. This gives usO(log mid * x)unique states aslimitis boolean and does not significantly increase the number of states.
Thus, the space complexity is O(log mid * x) for the memoization cache, combined with O(log mid) for the recursion stack, which leads us to O(log mid * (x + 1)) since x will generally be much larger than 1.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
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
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.