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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

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

Difficulty: Medium

Problem Description

You are given an integer k and an integer x. The price of a number num is calculated by the count of set bits at positions x, 2x, 3x, etc., in its binary representation. The accumulated price of num is the total price of numbers from 1 to num. num is considered cheap if its accumulated price is less than or equal to k. Return the greatest cheap number.

Key Insights

  • The price of a number is determined by the positions of set bits in its binary representation based on the value of x.
  • The accumulated price can be computed iteratively as we check each number.
  • The problem can be approached using binary search to efficiently find the maximum cheap number.

Space and Time Complexity

Time Complexity: O(n log n) where n is the maximum number checked. Space Complexity: O(1) as we are using only a constant amount of extra space.

Solution

To solve this problem, we can utilize binary search to find the maximum number that meets the criteria of being "cheap." The key steps in the solution include:

  1. Price Calculation: For any number, calculate its price based on the number of set bits at the specified positions defined by x.
  2. Accumulated Price Calculation: Keep a running total of the accumulated price for numbers from 1 up to num.
  3. Binary Search: Use binary search to efficiently determine the largest number for which the accumulated price is less than or equal to k.

By applying these steps, we can quickly zero in on the maximum cheap number.

Code Solutions

def count_set_bits(num, x):
    price = 0
    position = x
    while position <= num:
        if num & position:
            price += 1
        position <<= 1
    return price

def accumulated_price(num, x):
    total_price = 0
    for i in range(1, num + 1):
        total_price += count_set_bits(i, x)
    return total_price

def max_cheap_number(k, x):
    left, right = 1, k
    result = 0
    while left <= right:
        mid = (left + right) // 2
        if accumulated_price(mid, x) <= k:
            result = mid
            left = mid + 1
        else:
            right = mid - 1
    return result
← Back to All Questions