Maximum Number That Sum of the Prices Is Less Than or Equal to K
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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 | 0 0 0 0 0** 1**** 1** 0** 1** | 3 |
| 2 | 13 | 0 0 0 0 0** 1** 1 0 1 | 1 |
| 2 | 233 | 0** 1** 1** 1** 0** 1** 0 0 1 | 3 |
| 3 | 13 | 0 00 0 01** 1** 01 | 1 |
| 3 | 362 | 1 01** 1** 01 0 10 | 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.
Examples
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 | 0 0** 1** | 1 | 1 |
| 1 | 2 | 0** 1** 0 | 1 | 2 |
| 1 | 3 | 0** 1**** 1** | 2 | 4 |
| 1 | 4 | 1 0 0 | 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 | 0 0 0 1 | 0 | 0 |
| 2 | 2 | 0 0** 1** 0 | 1 | 1 |
| 2 | 3 | 0 0** 1** 1 | 1 | 2 |
| 2 | 4 | 0 1 0 0 | 0 | 2 |
| 2 | 5 | 0 1 0 1 | 0 | 2 |
| 2 | 6 | 0 1** 1** 0 | 1 | 3 |
| 2 | 7 | 0 1** 1** 1 | 1 | 4 |
| 2 | 8 | 1 0 0 0 | 1 | 5 |
| 2 | 9 | 1 0 0 1 | 1 | 6 |
| 2 | 10 | 1 0** 1** 0 | 2 | 8 |
Constraints
1 <= k <= 10151 <= x <= 8
Solution
Method 1 – Binary Search with Bit Manipulation
Intuition
The price of a number is the count of set bits at positions x, 2x, 3x, ... in its binary representation. The accumulated price is the sum of prices from 1 to num. We want the largest num such that the accumulated price is at most k. Since the price function is monotonic, we can use binary search.
Approach
- Define a function to compute the price of a number: count set bits at positions
x, 2x, 3x, .... - Define a function to compute the accumulated price up to
num. - Use binary search on
numin the range[1, 2*k](since price per number is at least 0 and at most the number of bits). - For each mid, compute the accumulated price. If it is
<= k, move right; else, move left. - Return the largest
numfound.
Code
C++
class Solution {
public:
long long price(int num, int x) {
long long res = 0;
for (int i = x - 1; i < 60; i += x) {
if (num & (1LL << i)) res++;
}
return res;
}
long long acc_price(int num, int x) {
long long res = 0;
for (int i = 1; i <= num; ++i) res += price(i, x);
return res;
}
int maximumNumber(long long k, int x) {
int l = 1, r = 2e6, ans = 0;
while (l <= r) {
int m = l + (r - l) / 2;
if (acc_price(m, x) <= k) { ans = m; l = m + 1; }
else r = m - 1;
}
return ans;
}
};
Go
func price(num, x int) int64 {
var res int64
for i := x - 1; i < 60; i += x {
if num&(1<<i) != 0 {
res++
}
}
return res
}
func accPrice(num, x int) int64 {
var res int64
for i := 1; i <= num; i++ {
res += price(i, x)
}
return res
}
func maximumNumber(k int64, x int) int {
l, r, ans := 1, 2000000, 0
for l <= r {
m := (l + r) / 2
if accPrice(m, x) <= k {
ans = m
l = m + 1
} else {
r = m - 1
}
}
return ans
}
Java
class Solution {
private long price(int num, int x) {
long res = 0;
for (int i = x - 1; i < 60; i += x) {
if (((num >> i) & 1) != 0) res++;
}
return res;
}
private long accPrice(int num, int x) {
long res = 0;
for (int i = 1; i <= num; i++) res += price(i, x);
return res;
}
public int maximumNumber(long k, int x) {
int l = 1, r = 2000000, ans = 0;
while (l <= r) {
int m = l + (r - l) / 2;
if (accPrice(m, x) <= k) { ans = m; l = m + 1; }
else r = m - 1;
}
return ans;
}
}
Kotlin
class Solution {
private fun price(num: Int, x: Int): Long {
var res = 0L
var i = x - 1
while (i < 60) {
if ((num shr i) and 1 != 0) res++
i += x
}
return res
}
private fun accPrice(num: Int, x: Int): Long {
var res = 0L
for (i in 1..num) res += price(i, x)
return res
}
fun maximumNumber(k: Long, x: Int): Int {
var l = 1
var r = 2000000
var ans = 0
while (l <= r) {
val m = (l + r) / 2
if (accPrice(m, x) <= k) {
ans = m
l = m + 1
} else {
r = m - 1
}
}
return ans
}
}
Python
class Solution:
def price(self, num: int, x: int) -> int:
res = 0
i = x - 1
while i < 60:
if (num >> i) & 1:
res += 1
i += x
return res
def acc_price(self, num: int, x: int) -> int:
res = 0
for i in range(1, num + 1):
res += self.price(i, x)
return res
def maximumNumber(self, k: int, x: int) -> int:
l, r, ans = 1, 2_000_000, 0
while l <= r:
m = (l + r) // 2
if self.acc_price(m, x) <= k:
ans = m
l = m + 1
else:
r = m - 1
return ans
Rust
impl Solution {
pub fn maximum_number(k: i64, x: i32) -> i32 {
fn price(num: i32, x: i32) -> i64 {
let mut res = 0;
let mut i = x - 1;
while i < 60 {
if (num >> i) & 1 != 0 {
res += 1;
}
i += x;
}
res
}
fn acc_price(num: i32, x: i32) -> i64 {
let mut res = 0;
for i in 1..=num {
res += price(i, x);
}
res
}
let (mut l, mut r, mut ans) = (1, 2_000_000, 0);
while l <= r {
let m = (l + r) / 2;
if acc_price(m, x) <= k {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
ans
}
}
TypeScript
class Solution {
price(num: number, x: number): number {
let res = 0;
for (let i = x - 1; i < 60; i += x) {
if ((num >> i) & 1) res++;
}
return res;
}
accPrice(num: number, x: number): number {
let res = 0;
for (let i = 1; i <= num; i++) res += this.price(i, x);
return res;
}
maximumNumber(k: number, x: number): number {
let l = 1, r = 2_000_000, ans = 0;
while (l <= r) {
const m = Math.floor((l + r) / 2);
if (this.accPrice(m, x) <= k) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n * (60/x) * log n)— For each binary search step, we sum prices up ton(can be optimized for largek). - 🧺 Space complexity:
O(1)— Only a few variables are used.