3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K
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, starting from the least significant bit. The following table contains examples of how price is calculated.
| x | num | Binary Representation | Price |
|---|---|---|---|
| 1 | 13 | 000001101 | 3 |
| 2 | 13 | 000001101 | 1 |
| 2 | 233 | 011101001 | 3 |
| 3 | 13 | 000001101 | 1 |
| 3 | 362 | 101101010 | 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 | 001 | 1 | 1 |
| 1 | 2 | 010 | 1 | 2 |
| 1 | 3 | 011 | 2 | 4 |
| 1 | 4 | 100 | 1 | 5 |
| 1 | 5 | 101 | 2 | 7 |
| 1 | 6 | 110 | 2 | 9 |
| 1 | 7 | 111 | 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 | 0010 | 1 | 1 |
| 2 | 3 | 0011 | 1 | 2 |
| 2 | 4 | 0100 | 0 | 2 |
| 2 | 5 | 0101 | 0 | 2 |
| 2 | 6 | 0110 | 1 | 3 |
| 2 | 7 | 0111 | 1 | 4 |
| 2 | 8 | 1000 | 1 | 5 |
| 2 | 9 | 1001 | 1 | 6 |
| 2 | 10 | 1010 | 2 | 8 |
Constraints:
1 <= k <= 10151 <= x <= 8
Solutions
Solution 1: Binary Search + Digit DP
We notice that if $\textit{num}$ increases, the total value from $1$ to $\textit{num}$ also increases. Therefore, we can use a binary search method to find the largest cheap number.
We define the left boundary of the binary search as $l = 1$. Since there is at least one valuable number in every $2^x + 1$ numbers, and the total value does not exceed $10^{15}$, we can set the right boundary of the binary search as $r = 10^{18}$.
Next, we perform a binary search. For each $\textit{mid}$, we use the digit DP method to calculate the total value from $1$ to $\textit{mid}$. If the total value does not exceed $k$, it means $\textit{mid}$ is a cheap number, and we update the left boundary $l$ to $\textit{mid}$. Otherwise, we update the right boundary $r$ to $\textit{mid} - 1$.
Finally, we return the left boundary $l$.
The time complexity is $O(\log^2 k)$, and the space complexity is $O(\log k)$.
Python3
class Solution:
def findMaximumNumber(self, k: int, x: int) -> int:
@cache
def dfs(pos, limit, cnt):
if pos == 0:
return cnt
ans = 0
up = (self.num >> (pos - 1) & 1) if limit else 1
for i in range(up + 1):
ans += dfs(pos - 1, limit and i == up, cnt + (i == 1 and pos % x == 0))
return ans
l, r = 1, 10**18
while l < r:
mid = (l + r + 1) >> 1
self.num = mid
v = dfs(mid.bit_length(), True, 0)
dfs.cache_clear()
if v <= k:
l = mid
else:
r = mid - 1
return l
Java
class Solution {
private int x;
private long num;
private Long[][] f;
public long findMaximumNumber(long k, int x) {
this.x = x;
long l = 1, r = (long) 1e17;
while (l < r) {
long mid = (l + r + 1) >>> 1;
num = mid;
f = new Long[65][65];
int pos = 64 - Long.numberOfLeadingZeros(mid);
if (dfs(pos, 0, true) <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
private long dfs(int pos, int cnt, boolean limit) {
if (pos == 0) {
return cnt;
}
if (!limit && f[pos][cnt] != null) {
return f[pos][cnt];
}
long ans = 0;
int up = limit ? (int) (num >> (pos - 1) & 1) : 1;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0 ? 1 : 0), limit && i == up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
}
}
C++
class Solution {
public:
long long findMaximumNumber(long long k, int x) {
using ll = long long;
ll l = 1, r = 1e17;
ll num = 0;
ll f[65][65];
auto dfs = [&](this auto&& dfs, int pos, int cnt, bool limit) -> ll {
if (pos == 0) {
return cnt;
}
if (!limit && f[pos][cnt] != -1) {
return f[pos][cnt];
}
int up = limit ? num >> (pos - 1) & 1 : 1;
ll ans = 0;
for (int i = 0; i <= up; ++i) {
ans += dfs(pos - 1, cnt + (i == 1 && pos % x == 0), limit && i == up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
};
while (l < r) {
ll mid = (l + r + 1) >> 1;
num = mid;
memset(f, -1, sizeof(f));
int pos = 64 - __builtin_clzll(mid);
if (dfs(pos, 0, true) <= k) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
};
Go
func findMaximumNumber(k int64, x int) int64 {
var l, r int64 = 1, 1e17
var num int64
var f [65][65]int64
var dfs func(pos, cnt int, limit bool) int64
dfs = func(pos, cnt int, limit bool) int64 {
if pos == 0 {
return int64(cnt)
}
if !limit && f[pos][cnt] != -1 {
return f[pos][cnt]
}
var ans int64
up := 1
if limit {
up = int(num >> (pos - 1) & 1)
}
for i := 0; i <= up; i++ {
v := cnt
if i == 1 && pos%x == 0 {
v++
}
ans += dfs(pos-1, v, limit && i == up)
}
if !limit {
f[pos][cnt] = ans
}
return ans
}
for l < r {
mid := (l + r + 1) >> 1
num = mid
m := bits.Len(uint(num))
for i := range f {
for j := range f[i] {
f[i][j] = -1
}
}
if dfs(m, 0, true) <= k {
l = mid
} else {
r = mid - 1
}
}
return l
}
TypeScript
function findMaximumNumber(k: number, x: number): number {
let [l, r] = [1n, 10n ** 17n];
let num: bigint;
const f: bigint[][] = Array.from({ length: 65 }, () => Array(65).fill(-1n));
const dfs = (pos: number, cnt: number, limit: boolean): bigint => {
if (pos === 0) {
return BigInt(cnt);
}
if (!limit && f[pos][cnt] !== -1n) {
return f[pos][cnt];
}
let ans: bigint = 0n;
let up: number = 1;
if (limit) {
up = Number((num >> BigInt(pos - 1)) & 1n);
}
for (let i = 0; i <= up; i++) {
let v: number = cnt;
if (i === 1 && pos % x === 0) {
v++;
}
ans += dfs(pos - 1, v, limit && i === up);
}
if (!limit) {
f[pos][cnt] = ans;
}
return ans;
};
while (l < r) {
let mid: bigint = (l + r + 1n) >> 1n;
num = mid;
let m: number = num.toString(2).length;
for (let i = 0; i < f.length; i++) {
f[i].fill(-1n);
}
if (dfs(m, 0, true) <= BigInt(k)) {
l = mid;
} else {
r = mid - 1n;
}
}
return Number(l);
}