Maximum Number That Sum of the Prices Is Less Than or Equal to K
Source: leetcode
Difficulty: Medium
Tags: binary-search, dynamic-programming, bit-manipulation

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, starting from the least significant bit. The following table contains examples of how price is calculated.




| x | num | Binary Representation | Price |
| --- | --- | --- | --- |
| 1 | 13 | 00000**1****1**0**1** | 3 |
| 2 | 13 | 00000**1**101 | 1 |
| 2 | 233 | 0**1**1**1**0**1**001 | 3 |
| 3 | 13 | 000001**1**01 | 1 |
| 3 | 362 | **1**01**1**01010 | 2 |


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.


 


**Example 1:**



**Input:** k \= 9, x \= 1


**Output:** 6


**Explanation:**


As shown in the table below, `6` is the greatest cheap number.




| x | num | Binary Representation | Price | Accumulated Price |
| --- | --- | --- | --- | --- |
| 1 | 1 | 00**1** | 1 | 1 |
| 1 | 2 | 0**1**0 | 1 | 2 |
| 1 | 3 | 0**1****1** | 2 | 4 |
| 1 | 4 | **1**00 | 1 | 5 |
| 1 | 5 | **1**0**1** | 2 | 7 |
| 1 | 6 | **1****1**0 | 2 | 9 |
| 1 | 7 | **1****1****1** | 3 | 12 |



**Example 2:**



**Input:** k \= 7, x \= 2


**Output:** 9


**Explanation:**


As shown in the table below, `9` is the greatest cheap number.




| x | num | Binary Representation | Price | Accumulated Price |
| --- | --- | --- | --- | --- |
| 2 | 1 | 0001 | 0 | 0 |
| 2 | 2 | 00**1**0 | 1 | 1 |
| 2 | 3 | 00**1**1 | 1 | 2 |
| 2 | 4 | 0100 | 0 | 2 |
| 2 | 5 | 0101 | 0 | 2 |
| 2 | 6 | 01**1**0 | 1 | 3 |
| 2 | 7 | 01**1**1 | 1 | 4 |
| 2 | 8 | **1**000 | 1 | 5 |
| 2 | 9 | **1**001 | 1 | 6 |
| 2 | 10 | **1**0**1**0 | 2 | 8 |



 


**Constraints:**


- `1 <= k <= 1015`
- `1 <= x <= 8`




C++ solution:
#define ll long long
class Solution 
{
public:
    ll findMaximumNumber(ll k, int x) 
    {
        ios::sync_with_stdio(false); cin.tie(0);
        
        ll left = 1, right = 1e15;
        while (left <= right)
        {
            ll mid = (left+right)/2;
            if (solve(mid, x) <= k) left = mid+1;
            else right = mid-1;
        }
        return right;
    }
private:
    ll power2(int i)
    {
        return 1LL << i;
    }
    ll solve(ll num, int x)
    {
        int len = 0;
        ll tmp = num;
        while (tmp)
        {
            tmp = tmp >> 1;
            len++;
        }
        len -= (len%x);
        ll res = 0;
        num++;
        while (len > 0)
        {
            res += (num/power2(len)) * power2(len-1) + max(0LL, (num%power2(len)) - power2(len-1));
            len -= x;
        }   
        return res;
    }
};

Go solution:
func findMaximumNumber(k int64, x int) int64 {
  var left, right int64
  left, right = 1, int64(1e15)
  for left < right {
    mid := (right-left)/2 + left
    var priceSum int64
    var i int64
    // We try every bit position that must be set start from x and
    // we calculate the total numbers (up to mid) that have the current bit set.
    for i = int64(x); i < 60; i = i + int64(x) {
      priceSum += calc(mid, i)
    }
    if priceSum > k {
      right = mid
    } else {
      left = mid + 1
    }
  }
  return left - 1
}

// calc computes the numbers where the ith bit is set until num
func calc(num int64, i int64) int64 {
  var res int64
  num = num+1 // include 0 since that also contributes to the pattern
  plen := int64(1) << int64(i) // pattern length 01, 0011, 00001111, etc.
  p := num / plen       // number of full patterns
  res = p * plen/2      // number of ones in these patterns
  // We now also have to compute the remaining
  num %= plen
  // We have to subtract the number of zeros since they start with zeros
  // We have up to plen/2 zeros. num - plen/2 may be negative if the remaining
  // partial block is not even sufficient to host the zeros so we don't take
  // this into account.
  res = res + max(0, num - plen/2)
  return res
}

Java solution:
class Solution {
    private long getCurrSum(long num, int x) {
        long count = 0;
        for (int b = x - 1; b < 60; b += x) {
			// This gives the count of full cycles of bits in the binary representation of numbers from 1 to num.
            long fullCycles = num / (1L << (b + 1)); 
			//  count of set bits at the current position, given by (1L << b).
            count += fullCycles * (1L << b); 
			 // Calculate the remaining bits after the full cycles 
            long remaining = num % (1L << (b + 1));
			 // This part ensures that only the relevant remaining bits are considered, and any excess bits are ignored.
            count += Math.max(0, remaining - (1L << b));
        }
        return count;
    }
	
    public long findMaximumNumber(long k, int x) {
        long l = 1, r = (long) 1e15, result = 0;
        while (l <= r) {
            long mid = l + (r - l) / 2;
            if (getCurrSum(mid + 1, x) <= k) {
                result = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return result;
    }
}

JavaScript solution:
/**
 * @param {number} k
 * @param {number} x
 * @return {number}
 */
function findMaximumNumber(k, x) {
    let l = 1n;
    let r = 1000000000000000n;

    while (l < r) {
        let m = (l + r + 1n) / 2n;
        if (getSumPrices(m, x) > k)
            r = m - 1n;
        else
            l = m;
    }

    return Number(l);
}

// Returns the sum of prices of all numbers from 1 to `num`.
function getSumPrices(num, x) {
    let sumPrices = 0n;
    num++; // Increment `num` to account the 0-th row in the count of groups.
    for (let i = leftmostColumnIndex(num); i > 0; --i) {
        if (i % x === 0) {
            let groupSize = 1n << BigInt(i);
            let halfGroupSize = 1n << BigInt(i - 1);
            sumPrices += num / groupSize * halfGroupSize;
            let remainder = num % groupSize;
            sumPrices += remainder >= halfGroupSize ? remainder - halfGroupSize : 0n;
        }
    }
    return sumPrices;
}

// Returns the leftmost column index in 1-indexed.
function leftmostColumnIndex(num) {
    return num.toString(2).length;
}

Python solution:
class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        i = 0
        prev = 0
        cur = 0
        cache = [0]
        price = 0
        while price < k:
            i += 1
            if i % x == 0:
                cur = price + (1 << (i-1))
            else:
                cur = price
            #print(i, price, 1 << (i-1), cur)
            if price + cur > k:
                break
            price += cur
            #prev = cur
            cache.append(price)
        print(cache)
        print(1 << i, price)
        if price == k:
            base = (1 << i) - 1
        else:
            base = (1 << (i - 1)) - 1
        m = len(cache)
        #print(base, price, m-1, cache[m-1])
        j = m - 1
        left1 = 1 if m % x == 0 else 0
        while price <= k and j >= 0:
            while j >= 0:
                if price + (cache[j] + left1 * (1 << j)) <= k:
                    break
                j -= 1
            if j < 0:
                break
            #print(price, j, cache[j],  left1 * (1 << j))
            price += (cache[j] + left1 * (1 << j))
            base += (1 << j)
            if (j+1) % x == 0:
                left1 += 1
        #print(base, price)
        return base

Ruby solution:
def find_maximum_number(k, x)
  left = 1
  right = 10**18
  best = 0

  while left <= right
    mid = (left + right) / 2
    sum = 0
    i = x
    max_bit = mid.bit_length

    while i <= max_bit
      cycle = 1 << i
      half = cycle >> 1
      full_cycles = (mid + 1) / cycle
      count = full_cycles * half
      remainder = (mid + 1) % cycle
      count += [remainder - half, 0].max
      sum += count
      i += x
    end

    if sum <= k
      best = mid
      left = mid + 1
    else
      right = mid - 1
    end
  end

  best
end