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

MediumBit ManipulationBinary SearchDynamic Programming

Leetcode Link

Problem Description

You need to find the greatest "cheap" number based on a special pricing system.

How the pricing works:

Given two integers k and x
For any number num, its price is calculated by counting set bits (1s) at specific positions in its binary representation
The positions checked are: x, 2x, 3x, 4x, ... (multiples of x)
Positions are counted from the right, starting at position 1 (least significant bit)

Examples of price calculation:

When x = 1 and num = 13 (binary: 1101):
- Check positions 1, 2, 3, 4, ... from the right
- Positions 1, 3, and 4 have set bits
- Price = 3
When x = 2 and num = 13 (binary: 1101):
- Check positions 2, 4, 6, ... from the right
- Only position 4 has a set bit
- Price = 1

Accumulated price and cheap numbers:

The accumulated price of a number num is the sum of prices of all numbers from 1 to num
A number is considered cheap if its accumulated price is less than or equal to k
You need to return the greatest cheap number

For example, if k = 10 and x = 2, you need to find the largest number num such that the sum of prices of all numbers from 1 to num is at most 10.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The key observation is that as numbers increase, their accumulated price (sum of prices from 1 to that number) also increases monotonically. This monotonic property immediately suggests binary search as a potential approach - we can search for the boundary where numbers transition from "cheap" to "expensive".

To use binary search, we need to efficiently calculate the accumulated price for any given number num. Computing the price for each individual number from 1 to num would be too slow for large values. This is where digit DP comes in.

Digit DP is perfect for counting problems involving binary representations. We can think of building numbers from 1 to num digit by digit (bit by bit) and count how many times we encounter set bits at positions that are multiples of x. The beauty of digit DP is that it can calculate the total contribution of all numbers up to num in logarithmic time relative to the number of bits.

The approach works by:

Using binary search to find the maximum num where accumulated price ≤ k
For each candidate mid in binary search, using digit DP to calculate the total count of set bits at positions x, 2x, 3x, etc., across all numbers from 1 to mid
The digit DP traverses the binary representation from most significant to least significant bit, keeping track of:
- Current position (pos)
- Whether we're still bounded by mid's digits (limit)
- Count of valuable bits encountered so far (cnt)

The search space is bounded by 10^18 because with at most 10^15 as the maximum accumulated price, and considering that valuable bits appear regularly in the binary representations, this upper bound ensures we won't miss the answer.

Learn more about Binary Search and Dynamic Programming patterns.

Solution Approach

The solution uses binary search combined with digit DP to find the greatest cheap number.

Binary Search Setup:

Initialize search range: l = 1 (left boundary) and r = 10^18 (right boundary)
The right boundary r = 10^18 is chosen because with at most k ≤ 10^15 and the distribution of valuable bits, this ensures we won't miss the answer
For each candidate mid, check if its accumulated price is ≤ k
If yes, update l = mid (this number is cheap, try larger)
If no, update r = mid - 1 (this number is too expensive, try smaller)

Digit DP Implementation: The dfs function calculates the total count of valuable bits from all numbers from 1 to self.num:

@cache
def dfs(pos, limit, cnt):

Parameters:

pos: Current bit position being processed (from left to right)
limit: Boolean flag indicating if we're still bounded by self.num's digits
cnt: Count of valuable bits encountered in the current number being formed

How the DP works:

Base case: When pos == 0, we've processed all bits, return the count cnt
Determine upper bound for current bit:
- If limit is True: we can only use bits up to what's in self.num at position pos-1
- If limit is False: we can use either 0 or 1
Recursive transition:
- Try each valid bit value i (0 or 1)
- Update count: add 1 if i == 1 and current position is valuable (pos % x == 0)
- Update limit: remains True only if we're at limit and chose the maximum bit
Memoization: The @cache decorator stores results to avoid recomputation

Main algorithm flow:

while l < r:
    mid = (l + r + 1) >> 1  # [Binary search](/problems/binary-search-speedrun) middle point
    self.num = mid
    v = dfs(mid.bit_length(), True, 0)  # Calculate accumulated price
    dfs.cache_clear()  # Clear cache for next iteration
    if v <= k:
        l = mid  # mid is cheap, try larger
    else:
        r = mid - 1  # mid is too expensive, try smaller

The (l + r + 1) >> 1 ensures we round up when calculating mid to avoid infinite loops when l and r are adjacent.

After the binary search converges, l contains the greatest cheap number.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example with k = 9 and x = 2.

Step 1: Understanding what we're looking for

We need to find the largest number whose accumulated price ≤ 9
Valuable bit positions are 2, 4, 6, ... (multiples of 2)

Step 2: Binary Search Process

Initial range: l = 1, r = 10^18

First iteration:

mid = (1 + 10^18 + 1) >> 1 ≈ 5×10^17
This is clearly too large (accumulated price would be huge)
Update: r = 5×10^17 - 1

After several iterations, let's focus on when we get closer to the answer:

When checking mid = 7 (binary: 111):

Use digit DP to calculate accumulated price from 1 to 7
For each number 1-7, count bits at positions 2, 4:
- 1 (001): position 2 has 0 → price = 0
- 2 (010): position 2 has 1 → price = 1
- 3 (011): position 2 has 1 → price = 1
- 4 (100): position 2 has 0, position 4 has 1 → price = 1
- 5 (101): position 2 has 0, position 4 has 1 → price = 1
- 6 (110): position 2 has 1, position 4 has 1 → price = 2
- 7 (111): position 2 has 1, position 4 has 1 → price = 2
Total accumulated price = 0+1+1+1+1+2+2 = 8
Since 8 ≤ 9, update l = 7

When checking mid = 8 (binary: 1000):

Digit DP calculates accumulated price from 1 to 8
Number 8 itself has price = 0 (no bits at positions 2 or 4)
Total accumulated price = 8 + 0 = 8
Since 8 ≤ 9, update l = 8

When checking mid = 9 (binary: 1001):

Number 9 has price = 0 (no bits at positions 2 or 4)
Total accumulated price = 8 + 0 = 8
Since 8 ≤ 9, update l = 9

When checking mid = 10 (binary: 1010):

Number 10 has price = 1 (bit at position 2)
Total accumulated price = 8 + 0 + 1 = 9
Since 9 ≤ 9, update l = 10

When checking mid = 11 (binary: 1011):

Number 11 has price = 1 (bit at position 2)
Total accumulated price = 9 + 1 = 10
Since 10 > 9, update r = 10

Step 3: Binary search converges

Final answer: l = 10

How Digit DP works for calculating accumulated price of 7:

The digit DP builds numbers bit by bit from left to right. For num = 7 (binary: 111):

Start at position 3 (most significant bit)
For each position, decide whether to place 0 or 1
Track if we're still bounded by 7's bits (limit)
Count valuable bits (at positions 2, 4, etc.)

The DP efficiently counts all combinations:

Numbers starting with 0__ (1-3): explores all valid combinations
Numbers starting with 10_ (4-5): explores combinations
Numbers starting with 11_ (6-7): explores remaining combinations

By memoizing intermediate results, we avoid recalculating the same subproblems, making the computation efficient even for large numbers.

Solution Implementation

1class Solution:
2    def findMaximumNumber(self, k: int, x: int) -> int:
3        """
4        Find the maximum number where the sum of price bits does not exceed k.
5        Price bits are the bits at positions that are multiples of x.
6      
7        Args:
8            k: Maximum allowed sum of price bits
9            x: Position multiplier for price bits
10      
11        Returns:
12            Maximum number satisfying the constraint
13        """
14        from functools import cache
15      
16        @cache
17        def count_price_bits(bit_position: int, is_limited: bool, price_count: int) -> int:
18            """
19            Count total price bits using digit DP approach.
20          
21            Args:
22                bit_position: Current bit position being processed (1-indexed)
23                is_limited: Whether we're limited by the original number's bit at this position
24                price_count: Count of price bits accumulated so far
25          
26            Returns:
27                Total count of price bits for all numbers formed
28            """
29            # Base case: reached the end of bits
30            if bit_position == 0:
31                return price_count
32          
33            total_price_bits = 0
34          
35            # Determine upper bound for current bit
36            # If limited, use the actual bit value from self.current_number
37            # Otherwise, we can use 1 (maximum bit value)
38            upper_bound = (self.current_number >> (bit_position - 1) & 1) if is_limited else 1
39          
40            # Try all possible bit values at current position
41            for bit_value in range(upper_bound + 1):
42                # Check if current position contributes to price
43                # (position is multiple of x and bit is 1)
44                is_price_bit = (bit_value == 1 and bit_position % x == 0)
45                new_price_count = price_count + (1 if is_price_bit else 0)
46              
47                # Recursively process next bit position
48                # Remain limited only if we chose the maximum allowed bit value
49                still_limited = is_limited and (bit_value == upper_bound)
50                total_price_bits += count_price_bits(
51                    bit_position - 1, 
52                    still_limited, 
53                    new_price_count
54                )
55          
56            return total_price_bits
57      
58        # Binary search for the maximum number
59        left, right = 1, 10**18
60      
61        while left < right:
62            # Calculate mid point (using bit shift for division)
63            mid = (left + right + 1) >> 1
64          
65            # Set current number for DP calculation
66            self.current_number = mid
67          
68            # Calculate total price bits for all numbers from 1 to mid
69            total_price = count_price_bits(
70                mid.bit_length(),  # Start from most significant bit
71                True,               # Initially limited by mid's bits
72                0                   # No price bits counted yet
73            )
74          
75            # Clear cache for next iteration
76            count_price_bits.cache_clear()
77          
78            # Binary search logic
79            if total_price <= k:
80                # Can potentially go higher
81                left = mid
82            else:
83                # Need to go lower
84                right = mid - 1
85      
86        return left
87

1class Solution {
2    private int x;                    // The x-th bit position to count (every x-th bit)
3    private long currentNumber;       // Current number being evaluated in binary search
4    private Long[][] memo;             // Memoization table for dynamic programming
5  
6    /**
7     * Finds the maximum number such that the sum of price values <= k
8     * Price value is the count of set bits at positions that are multiples of x
9     * 
10     * @param k Maximum allowed sum of price values
11     * @param x Check every x-th bit position (1-indexed from right)
12     * @return Maximum number satisfying the condition
13     */
14    public long findMaximumNumber(long k, int x) {
15        this.x = x;
16      
17        // Binary search for the answer in range [1, 10^17]
18        long left = 1;
19        long right = (long) 1e17;
20      
21        while (left < right) {
22            // Calculate mid with overflow protection
23            long mid = (left + right + 1) >>> 1;
24            currentNumber = mid;
25          
26            // Initialize memoization table for digit DP
27            // 65 positions for bits (enough for 64-bit numbers)
28            memo = new Long[65][65];
29          
30            // Find the position of the most significant bit
31            int bitPosition = 64 - Long.numberOfLeadingZeros(mid);
32          
33            // Calculate total price sum for all numbers from 1 to mid
34            long totalPriceSum = dfs(bitPosition, 0, true);
35          
36            if (totalPriceSum <= k) {
37                // If sum is within limit, try larger numbers
38                left = mid;
39            } else {
40                // If sum exceeds limit, try smaller numbers
41                right = mid - 1;
42            }
43        }
44      
45        return left;
46    }
47  
48    /**
49     * Digit DP to count the sum of price values for all numbers from 1 to currentNumber
50     * 
51     * @param position Current bit position being processed (1-indexed from right)
52     * @param priceCount Count of price bits accumulated so far for current number
53     * @param isLimit Whether we're still bounded by currentNumber's digits
54     * @return Total sum of price values for all valid numbers
55     */
56    private long dfs(int position, int priceCount, boolean isLimit) {
57        // Base case: processed all bit positions
58        if (position == 0) {
59            return priceCount;
60        }
61      
62        // Check memoization if not limited by upper bound
63        if (!isLimit && memo[position][priceCount] != null) {
64            return memo[position][priceCount];
65        }
66      
67        long totalSum = 0;
68      
69        // Determine the upper bound for current bit position
70        // If limited, use the bit from currentNumber; otherwise, can use 1
71        int upperBound = isLimit ? (int) ((currentNumber >> (position - 1)) & 1) : 1;
72      
73        // Try placing 0 or 1 at current bit position
74        for (int bitValue = 0; bitValue <= upperBound; ++bitValue) {
75            // Calculate new price count
76            // Add 1 if current bit is 1 and position is multiple of x
77            int newPriceCount = priceCount;
78            if (bitValue == 1 && position % x == 0) {
79                newPriceCount++;
80            }
81          
82            // Recursively process next bit position
83            // Remain limited only if we're at limit and chose the maximum bit value
84            totalSum += dfs(position - 1, newPriceCount, isLimit && bitValue == upperBound);
85        }
86      
87        // Memoize result if not limited (reusable state)
88        if (!isLimit) {
89            memo[position][priceCount] = totalSum;
90        }
91      
92        return totalSum;
93    }
94}
95

1class Solution {
2public:
3    long long findMaximumNumber(long long k, int x) {
4        using ll = long long;
5      
6        // Binary search range: find the maximum number
7        ll left = 1, right = 1e17;
8        ll currentNumber = 0;
9      
10        // DP memoization table: dp[position][count] = number of valid combinations
11        // position: current bit position being processed
12        // count: number of special bits counted so far
13        ll dp[65][65];
14      
15        // Digit DP function to count the sum of special bits for all numbers from 1 to currentNumber
16        // pos: current bit position (1-indexed from right)
17        // specialBitCount: count of special bits found so far
18        // isLimit: whether we're still bounded by currentNumber's digits
19        auto countSpecialBits = [&](this auto&& countSpecialBits, 
20                                    int pos, 
21                                    int specialBitCount, 
22                                    bool isLimit) -> ll {
23            // Base case: processed all bits
24            if (pos == 0) {
25                return specialBitCount;
26            }
27          
28            // Return memoized result if not limited by upper bound
29            if (!isLimit && dp[pos][specialBitCount] != -1) {
30                return dp[pos][specialBitCount];
31            }
32          
33            // Determine the upper bound for current bit
34            // If limited, use the bit from currentNumber; otherwise, can use 1
35            int upperBound = isLimit ? (currentNumber >> (pos - 1)) & 1 : 1;
36          
37            ll result = 0;
38          
39            // Try all possible bit values (0 or 1)
40            for (int bit = 0; bit <= upperBound; ++bit) {
41                // Count special bit if:
42                // 1. Current bit is 1
43                // 2. Position is divisible by x (positions that contribute to price)
44                int newSpecialBitCount = specialBitCount + 
45                                        (bit == 1 && pos % x == 0 ? 1 : 0);
46              
47                // Recursively process next position
48                // Remain limited only if we used the maximum bit value
49                result += countSpecialBits(pos - 1, 
50                                          newSpecialBitCount, 
51                                          isLimit && bit == upperBound);
52            }
53          
54            // Memoize result when not limited
55            if (!isLimit) {
56                dp[pos][specialBitCount] = result;
57            }
58          
59            return result;
60        };
61      
62        // Binary search for the maximum number whose total price <= k
63        while (left < right) {
64            ll mid = (left + right + 1) >> 1;  // Take upper middle to avoid infinite loop
65            currentNumber = mid;
66          
67            // Reset DP table for new number
68            memset(dp, -1, sizeof(dp));
69          
70            // Find the highest bit position in mid (number of bits)
71            int bitLength = 64 - __builtin_clzll(mid);
72          
73            // Check if the sum of special bits for all numbers from 1 to mid is <= k
74            if (countSpecialBits(bitLength, 0, true) <= k) {
75                left = mid;  // Can potentially go higher
76            } else {
77                right = mid - 1;  // Too high, search lower
78            }
79        }
80      
81        return left;
82    }
83};
84

1/**
2 * Finds the maximum number such that the sum of price values of all numbers 
3 * from 1 to that number is at most k.
4 * The price of a number is the count of set bits at positions that are multiples of x.
5 * 
6 * @param k - The maximum allowed sum of prices
7 * @param x - The position multiplier for counting set bits
8 * @returns The maximum number satisfying the condition
9 */
10function findMaximumNumber(k: number, x: number): number {
11    // Binary search range: from 1 to 10^17
12    let left: bigint = 1n;
13    let right: bigint = 10n ** 17n;
14  
15    // Current number being evaluated in binary search
16    let currentNumber: bigint;
17  
18    // Memoization table for dynamic programming
19    // dp[position][count] stores the sum of prices for all numbers with 'position' bits
20    // and 'count' set bits at positions divisible by x
21    const memoTable: bigint[][] = Array.from(
22        { length: 65 }, 
23        () => Array(65).fill(-1n)
24    );
25
26    /**
27     * Dynamic programming function to calculate the sum of prices
28     * for all numbers from 0 to currentNumber
29     * 
30     * @param position - Current bit position being processed (1-indexed from right)
31     * @param setBitCount - Count of set bits at positions divisible by x so far
32     * @param isLimit - Whether we're still bounded by currentNumber's bits
33     * @returns Sum of prices for all valid numbers
34     */
35    const calculatePriceSum = (
36        position: number, 
37        setBitCount: number, 
38        isLimit: boolean
39    ): bigint => {
40        // Base case: processed all bits
41        if (position === 0) {
42            return BigInt(setBitCount);
43        }
44      
45        // Use memoized result if not limited by currentNumber
46        if (!isLimit && memoTable[position][setBitCount] !== -1n) {
47            return memoTable[position][setBitCount];
48        }
49      
50        let totalSum: bigint = 0n;
51      
52        // Determine the upper bound for current bit
53        let upperBound: number = 1;
54        if (isLimit) {
55            // If limited, can't exceed the bit value in currentNumber
56            upperBound = Number((currentNumber >> BigInt(position - 1)) & 1n);
57        }
58      
59        // Try all possible bit values (0 or 1, up to upperBound)
60        for (let bitValue = 0; bitValue <= upperBound; bitValue++) {
61            let newSetBitCount: number = setBitCount;
62          
63            // If setting bit to 1 and position is divisible by x, increment count
64            if (bitValue === 1 && position % x === 0) {
65                newSetBitCount++;
66            }
67          
68            // Recursively calculate for remaining positions
69            totalSum += calculatePriceSum(
70                position - 1, 
71                newSetBitCount, 
72                isLimit && bitValue === upperBound
73            );
74        }
75      
76        // Memoize result if not limited
77        if (!isLimit) {
78            memoTable[position][setBitCount] = totalSum;
79        }
80      
81        return totalSum;
82    };
83
84    // Binary search for the maximum number
85    while (left < right) {
86        // Calculate middle point (using (left + right + 1) / 2 for upper mid)
87        let mid: bigint = (left + right + 1n) >> 1n;
88        currentNumber = mid;
89      
90        // Get the number of bits in binary representation
91        let bitLength: number = currentNumber.toString(2).length;
92      
93        // Reset memoization table for new calculation
94        for (let i = 0; i < memoTable.length; i++) {
95            memoTable[i].fill(-1n);
96        }
97      
98        // Check if sum of prices up to mid is within k
99        if (calculatePriceSum(bitLength, 0, true) <= BigInt(k)) {
100            // Can go higher, update left boundary
101            left = mid;
102        } else {
103            // Too high, update right boundary
104            right = mid - 1n;
105        }
106    }
107  
108    return Number(left);
109}
110

Time and Space Complexity

The time complexity is O(log^2 k). This comes from two nested logarithmic operations:

The binary search runs O(log k) iterations, as we search for the maximum number in the range [1, 10^18], and the answer is bounded by k
For each binary search iteration, the dfs function performs digit DP on a number with at most O(log k) bits (since the maximum valid number has magnitude proportional to k)
The dfs function visits each bit position once with at most 2 choices per position (0 or 1), resulting in O(log k) operations per binary search iteration
Combined: O(log k) × O(log k) = O(log^2 k)

The space complexity is O(log k). This is determined by:

The recursion depth of dfs which is equal to the bit length of the number being processed, at most O(log k)
The cache storage for memoization, which stores states for (pos, limit, cnt) tuples. Since pos has O(log k) values, limit has 2 values, and cnt can be at most O(log k), the cache size is bounded by O(log k)
The call stack depth during recursion is O(log k)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Binary Search Midpoint Calculation

Pitfall: Using mid = (left + right) // 2 when left < right can cause an infinite loop when left and right are adjacent numbers.

Example scenario:

When left = 5 and right = 6
Using (5 + 6) // 2 = 5 always gives mid = 5
If the condition passes (total_price <= k), we set left = mid = 5
The loop continues indefinitely since left never changes

Solution: Use mid = (left + right + 1) >> 1 to ensure rounding up:

# Correct approach - rounds up to avoid infinite loop
mid = (left + right + 1) >> 1

2. Forgetting to Clear the Cache Between Binary Search Iterations

Pitfall: The @cache decorator memoizes results based on function arguments. Since self.current_number changes between iterations but isn't a parameter to the cached function, stale cached values will give incorrect results.

Impact: The DP function returns cached results from previous mid values, leading to incorrect accumulated price calculations and wrong final answer.

Solution: Always clear the cache after each DP calculation:

total_price = count_price_bits(mid.bit_length(), True, 0)
count_price_bits.cache_clear()  # Essential - clear cache before next iteration

3. Off-by-One Error in Bit Position Indexing

Pitfall: Confusing 0-indexed and 1-indexed bit positions. The problem states positions are counted from the right starting at position 1, but bit operations typically use 0-indexing.

Wrong approach:

# Incorrect - treats position as 0-indexed
is_price_bit = (bit_value == 1 and (bit_position - 1) % x == 0)

Correct approach:

# Correct - position is already 1-indexed in our implementation
is_price_bit = (bit_value == 1 and bit_position % x == 0)

4. Incorrect Upper Bound Extraction in Digit DP

Pitfall: When determining the upper bound for the current bit, using the wrong bit shift operation or index.

Wrong approach:

# Incorrect - uses wrong indexing
upper_bound = (self.current_number >> bit_position & 1) if is_limited else 1

Correct approach:

# Correct - adjusts for 1-indexed positions
upper_bound = (self.current_number >> (bit_position - 1) & 1) if is_limited else 1

5. Not Handling the Edge Case When `k = 0`

Pitfall: The algorithm assumes we can always find at least one cheap number, but when k = 0, even the number 1 might be too expensive if its first bit is a price bit.

Solution: Add validation or handle the edge case:

if k == 0:
    # Check if even 1 is too expensive
    if x == 1:  # First bit is a price bit
        return 0  # No cheap numbers exist
    return 1  # Otherwise, 1 is cheap

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

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know