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.
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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
mid
by averagingl
andr
. For simplicity, let's suppose that our firstmid
is4
. - Now we use the DFS function to determine the cumulative price for all numbers up to
4
. - In binary, numbers from
1
to4
are1
,10
,11
, and100
. - The prices are based on set bits at even positions. So, the price of
1
is0
(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
1
to4
is0 + 1 + 1 + 0 = 2
, which is less thank=5
. - Since
2
is within our budget, we can safely movel
tomid
, to start checking bigger numbers.
Now, let's suppose l
is updated to 4
and repeat the process:
- Let's say our new
mid
is8
. - We again calculate the cumulative price for numbers
1
to8
. - The prices for numbers
5
to8
would be similarly calculated and the new total would include the sums from the previous step (1
to4
). - If this sum stays within
k=5
, we continue movingl
up. Otherwise, we would mover
down 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.
43
1class 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}
59
1class 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};
58
1type 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};
70
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
l
is 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, wheren
is the maximum value of the target number. -
Inside the binary search, we call the recursive
dfs
function, which is memoized to avoid redundant calculations. Thedfs
adds 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 thedfs
would 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 uniquepos
values is at mostlog mid
, and the number of uniquecnt
values is up tox
. This gives usO(log mid * x)
unique states aslimit
is 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.
In a binary min heap, the maximum element can be found in:
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
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!