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

1
2
3
4
5
6
7
8
9


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

1
2
3
4
5
6
7
8
9


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

  1. Define a function to compute the price of a number: count set bits at positions x, 2x, 3x, ....
  2. Define a function to compute the accumulated price up to num.
  3. Use binary search on num in the range [1, 2*k] (since price per number is at least 0 and at most the number of bits).
  4. For each mid, compute the accumulated price. If it is <= k, move right; else, move left.
  5. Return the largest num found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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 to n (can be optimized for large k).
  • 🧺 Space complexity: O(1) — Only a few variables are used.