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

Posted on 2024-11-30 Edited on 2025-02-12 In Leetcode

Description

You are given an integer k and an integer x. The price of a numbernum 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 ofnumis 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 <= 10^15
1 <= x <= 8

Hints/Notes

2024/11/23
Binary search + digit dp
0x3F’s solution(checked)
Weekly Contest 380

Solution

Language: C++

class Solution {
public:
    long long num;
    int x, n;
    vector<vector<long long>> dp;

    long long findMaximumNumber(long long k, int x) {
        this->x = x;
        // there is one elgible number every 2^x numbers
        long long left = 0, right = (k + 1) << x;
        while (left + 1 < right) {
            long long mid = left + (right - left) / 2;
            if (f(mid) > k) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return left;
    }

    long long f(long long num) {
        this->num = num;
        n = __lg(num);
        dp.resize(n + 1, vector<long long>(n + 1, -1));
        long long res = dfs(n, 0, true);
        return res;
    }

    long long dfs(int index, int price, int limit_high) {
        if (index == -1) {
            return price;
        }
        if (!limit_high && dp[index][price] != -1) {
            return dp[index][price];
        }
        int hi = limit_high ? (num >> index) & 1 : 1;
        long long res = 0;
        for (int i = 0; i <= hi; i++) {
            int tmp = 0;
            if ((index + 1) % x == 0) {
                tmp = i;
            }
            res += dfs(index - 1, price + tmp, limit_high && i == hi);
        }
        if (!limit_high) {
            dp[index][price] = res;
        }
        return res;
    }
};