Solution Approach

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

Binary Search Template Setup

We use the standard binary search template to find the first number that is too expensive:

left, right = 1, 10**18
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    total_price = calculate_price(mid)  # Using digit DP

    if total_price > k:  # feasible(mid) = "price exceeds k"
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

# first_true_index is the first expensive number
# Answer is first_true_index - 1 (last cheap number)

The feasible(mid) function returns True if the accumulated price > k (too expensive). This inverts the natural condition so we can use the standard "find first true" template.

Digit DP Implementation

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

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:

1. Base case: When pos == 0, we've processed all bits, return the count cnt

2. 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

3. 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

4. Memoization: The @cache decorator stores results to avoid recomputation

Final Result

After binary search completes:

• If first_true_index == 1, even number 1 is too expensive, return 0
• Otherwise, return first_true_index - 1 as the maximum cheap number

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):

1. Start at position 3 (most significant bit)
2. For each position, decide whether to place 0 or 1
3. Track if we're still bounded by 7's bits (limit)
4. 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.

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. Using Wrong Binary Search Template

Pitfall: Not using the standard binary search template with first_true_index tracking.

Common mistakes:

# WRONG: Using while left < right with different update rules
while left < right:
    mid = (left + right + 1) >> 1
    if total_price <= k:
        left = mid
    else:
        right = mid - 1

Correct approach using template:

# CORRECT: Standard template with first_true_index
left, right = 1, 10**18
first_true_index = -1

while left <= right:
    mid = (left + right) // 2
    if is_too_expensive(mid):  # True when price > k
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

return first_true_index - 1  # Last cheap number

2. Forgetting to Invert the Condition for "Find Maximum"

Pitfall: The template finds the first true position, but we need the last feasible position (maximum cheap number). Must invert the condition.

Wrong:

# WRONG: feasible returns True when number is cheap
def feasible(num):
    return calculate_price(num) <= k  # True = cheap

Correct:

# CORRECT: feasible returns True when number is TOO EXPENSIVE
def is_too_expensive(num):
    return calculate_price(num) > k  # True = too expensive

# Then: first_true_index - 1 = last cheap number

3. 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.

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

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

Pitfall: Confusing 0-indexed and 1-indexed bit positions.

Correct approach:

# Position is 1-indexed in our implementation
is_price_bit = (bit_value == 1 and bit_position % x == 0)
upper_bound = (self.current_number >> (bit_position - 1) & 1) if is_limited else 1

5. Not Handling Edge Cases

Pitfall: Not handling when first_true_index == 1 (even number 1 is too expensive).

Correct:

if first_true_index == 1:
    return 0  # No cheap numbers exist
return first_true_index - 1