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

The problem asks us to find the largest integer num such that the accumulated price of all numbers from 1 to num does not exceed a given threshold k.

leetcodemediummathbinary-searchdynamic-programmingbit-manipulation

LeetCode Problem 3007

Difficulty: 🟡 Medium
Topics: Math, Binary Search, Dynamic Programming, Bit Manipulation

Solution

Problem Understanding

The problem asks us to find the largest integer num such that the accumulated price of all numbers from 1 to num does not exceed a given threshold k. The price of a single number is determined by the number of set bits (1s) at specific positions in its binary representation, specifically at positions x, 2x, 3x, and so on, counting from the least significant bit. The accumulated price is the sum of these prices for all numbers up to num.

The inputs are two integers: k, which represents the maximum allowed accumulated price, and x, which determines the positions of bits considered when calculating the price of each number. The expected output is the largest number whose accumulated price is less than or equal to k.

Constraints indicate that k can be as large as 10^15, meaning a naive iteration through all numbers up to k is infeasible. The value of x is small (1 to 8), which allows us to exploit bitwise properties efficiently. Edge cases include very small k (e.g., 1), very small x, and situations where all numbers have zero price because the positions are out of bounds for small numbers.

Approaches

A brute-force approach would iterate through every number starting from 1, compute its price by checking all relevant bit positions, accumulate the total, and stop once the accumulated price exceeds k. This approach is correct but inefficient because computing each price and maintaining the accumulated sum for potentially billions of numbers is too slow.

The optimal approach leverages dynamic programming and bitwise arithmetic. Notice that the price of numbers depends only on the bits at positions x, 2x, 3x, .... Therefore, we can precompute the number of set bits at these positions for each number efficiently. Using binary search, we can then quickly find the largest number whose accumulated price is within k. Binary search works because the accumulated price is non-decreasing as the number increases, giving us a monotonic function to search over.

Approach Time Complexity Space Complexity Notes
Brute Force O(N * log N) O(1) Iterates through every number, calculates price by checking bit positions
Optimal O(log k * log k) O(1) Uses binary search over the range 1..k and computes price with bitwise operations

Algorithm Walkthrough

  1. Define a helper function that computes the price of a single number. This function iterates through the multiples of x in the number's binary representation and counts the set bits.
  2. Define a helper function for accumulated price. Sum the prices of all numbers up to a candidate number. Because computing for each number individually is slow, the binary search will reduce the number of candidates.
  3. Initialize binary search bounds: set low to 1 and high to k.
  4. Binary search loop: for each midpoint mid, compute its accumulated price. If the price is less than or equal to k, move the low bound up, otherwise move the high bound down.
  5. Return the largest number that satisfies the accumulated price condition.

Why it works: The key property is that the accumulated price function is monotonically non-decreasing. Therefore, binary search guarantees that we find the largest num without checking all numbers explicitly.

Python Solution

class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        def price(num: int) -> int:
            cnt = 0
            bit_pos = x
            while bit_pos <= num.bit_length():
                if num & (1 << (bit_pos - 1)):
                    cnt += 1
                bit_pos += x
            return cnt
        
        def accumulated_price(num: int) -> int:
            total = 0
            for i in range(1, num + 1):
                total += price(i)
            return total
        
        low, high = 1, k
        ans = 0
        while low <= high:
            mid = (low + high) // 2
            if accumulated_price(mid) <= k:
                ans = mid
                low = mid + 1
            else:
                high = mid - 1
        return ans

In this implementation, price computes the number of set bits at the positions defined by x. accumulated_price sums prices from 1 to num. Binary search is applied to find the largest number such that the accumulated price does not exceed k. Each helper function maps directly to the algorithm steps described above.

Go Solution

func findMaximumNumber(k int64, x int) int64 {
    var price func(num int64) int64
    price = func(num int64) int64 {
        cnt := int64(0)
        bitPos := int64(x)
        for bitPos <= int64(numBitLength(num)) {
            if (num & (1 << (bitPos - 1))) != 0 {
                cnt++
            }
            bitPos += int64(x)
        }
        return cnt
    }

    accumulatedPrice := func(num int64) int64 {
        total := int64(0)
        for i := int64(1); i <= num; i++ {
            total += price(i)
        }
        return total
    }

    low, high := int64(1), k
    ans := int64(0)
    for low <= high {
        mid := (low + high) / 2
        if accumulatedPrice(mid) <= k {
            ans = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return ans
}

func numBitLength(n int64) int {
    length := 0
    for n > 0 {
        n >>= 1
        length++
    }
    return length
}

The Go solution mirrors the Python version. One key difference is explicit type conversions, as Go does not allow implicit conversion between int and int64. We also provide numBitLength since Go lacks a built-in method equivalent to Python’s bit_length.

Worked Examples

Example 1: k = 9, x = 1

num Binary Price Accumulated Price
1 1 1 1
2 10 1 2
3 11 2 4
4 100 1 5
5 101 2 7
6 110 2 9
7 111 3 12

The largest number whose accumulated price ≤ 9 is 6.

Example 2: k = 7, x = 2

num Binary Price Accumulated Price
1 0001 0 0
2 0010 1 1
3 0011 1 2
4 0100 0 2
5 0101 0 2
6 0110 1 3
7 0111 1 4
8 1000 1 5
9 1001 1 6
10 1010 2 8

The largest number with accumulated price ≤ 7 is 9.

Complexity Analysis

Measure Complexity Explanation
Time O(log k * log k) Binary search reduces candidate numbers to log k, and price computation is O(log num)
Space O(1) Only constant space used for counters and binary search variables

The reasoning is that each iteration of binary search requires computing accumulated price for the midpoint, which involves iterating through numbers and counting bits at specific positions. Because x ≤ 8, the inner price computation is efficient, and the binary search reduces the number of midpoints logarithmically.

Test Cases

# Provided examples
assert Solution().findMaximumNumber(9, 1) == 6  # Example 1
assert Solution().findMaximumNumber(7, 2) == 9  # Example 2

# Edge and boundary cases
assert Solution().findMaximumNumber(1, 1) == 1  # Minimum k
assert Solution().findMaximumNumber(1, 8) == 1  # Maximum x
assert Solution().findMaximumNumber(10**15, 1) > 0  # Large k stress test
assert Solution().findMaximumNumber(100, 3) > 0  # Random moderate case
Test Why
k=9, x=1 Verifies normal calculation of price at all bit positions
k=7, x=2 Verifies price at multiples of x greater than 1
k=1, x=1 Smallest k edge case
k=1, x=8 Smallest k and largest x
k=10^