3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K

MediumBit ManipulationBinary SearchDynamic Programming

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 Evaluator

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 mid by averaging l and r. For simplicity, let's suppose that our first mid is 4.
Now we use the DFS function to determine the cumulative price for all numbers up to 4.
In binary, numbers from 1 to 4 are 1, 10, 11, and 100.
The prices are based on set bits at even positions. So, the price of 1 is 0 (no second bit), the price of 2 (10) is 1, the price of 3 (11) is 1 (only considering the second bit), and the price of 4 (100) is 0.
Thus, the cumulative price for numbers 1 to 4 is 0 + 1 + 1 + 0 = 2, which is less than k=5.
Since 2 is within our budget, we can safely move l to mid, to start checking bigger numbers.

Now, let's suppose l is updated to 4 and repeat the process:

Let's say our new mid is 8.
We again calculate the cumulative price for numbers 1 to 8.
The prices for numbers 5 to 8 would be similarly calculated and the new total would include the sums from the previous step (1 to 4).
If this sum stays within k=5, we continue moving l up. Otherwise, we would move r down to mid - 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 than r. The search space is reduced by half in each iteration. This results in a time complexity of O(log n) for the binary search, where n 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. The dfs 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 of mid, so the max depth of the recursion is O(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 the dfs would be O(2^(log mid)), which simplifies to O(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 is O(log mid).
The cache will store results for each unique state (pos, limit, cnt). The number of unique pos values is at most log mid, and the number of unique cnt values is up to x. This gives us O(log mid * x) unique states as limit 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don’t know