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 <= 1015
• 1 <= 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)$.

Python3JavaC++GoTypeScript

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

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;
    }
}

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 = [&](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(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(dfs, pos, 0, true) <= k) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
};

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
}

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);
}

Comments