We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

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

Number: 3240

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given two integers k and x. For any number num, its price is defined as the count of set bits in its binary representation at positions x, 2x, 3x, … (with the least significant bit considered as position 1). The accumulated price of num is the sum of prices of all numbers from 1 to num. A number num is considered cheap if its accumulated price is less than or equal to k. The task is to return the greatest cheap number.

Key Insights

  • The price of a single number is determined only by the bits in positions that are multiples of x.
  • The accumulated price function from 1 to num is monotonic (non-decreasing); hence binary search can be applied to find the maximum num such that its accumulated price ≤ k.
  • The contribution of each eligible bit position can be computed using a formula similar to counting set bits over a range. For a given bit position p (where p is a multiple of x), the count of ones among numbers from 1 to n is: • count = (n // (2^p)) * (2^(p-1)) + max(0, (n % (2^p)) − 2^(p-1) + 1)
  • Sum the contributions for positions p = x, 2x, 3x, … (as long as 2^(p-1) ≤ n) to get the accumulated price function.

Space and Time Complexity

Time Complexity: O(log(high) * (max_bits)), where max_bits is the number of bit positions to check (roughly O(log n) at worst).
Space Complexity: O(1)

Solution

The solution uses binary search over the candidate numbers. A helper function f(n) computes the accumulated price for numbers from 1 to n by iterating over every eligible bit position (multiples of x) and using the counting formula described above. Since the accumulated price is monotonic, we can use binary search to find the largest number num for which f(num) ≤ k.
Data structures used: basic integer arithmetic and loop iteration.
Algorithmic approaches: binary search and bit manipulation.
Key tricks include breaking down the accumulated price by bit positions and computing the count in each complete block plus the remaining (partial block) portion.

Code Solutions

# Python solution with line-by-line comments

def accumulated_price(n, x):
    total = 0
    j = 1
    # Loop over every multiple of x until the bit position exceeds what can be set by n
    while True:
        pos = j * x  # current bit position to check (1-indexed)
        # Calculate the value for one cycle: cycle = 2^pos and half_cycle = 2^(pos-1)
        cycle = 1 << pos         # 2^pos
        half_cycle = 1 << (pos - 1)  # 2^(pos-1)
        if half_cycle > n:
            break  # if the lowest value having a set bit at this position is greater than n, we stop
        # Full cycles in range [1, n]
        full_cycles = n // cycle
        count = full_cycles * half_cycle
        # Partial cycle remainder: numbers in the incomplete cycle may contribute
        remainder = n % cycle
        count += max(0, remainder - half_cycle + 1)
        total += count
        j += 1
    return total

def maximum_cheap_number(k, x):
    low, high = 0, 10**18  # high bound chosen large enough for constraints
    # Binary search for the maximum num such that accumulated_price(num, x) <= k
    while low < high:
        mid = (low + high + 1) // 2  # mid candidate (upper mid)
        if accumulated_price(mid, x) <= k:
            low = mid  # candidate is cheap so try for a larger number
        else:
            high = mid - 1  # candidate is too expensive; lower the search space
    return low

# Example usage:
# For k = 9, x = 1 -> expected output is 6
print(maximum_cheap_number(9, 1))
# For k = 7, x = 2 -> expected output is 9
print(maximum_cheap_number(7, 2))
← Back to All Questions