Algorithms
Medium
3007
3240
Maximum Number That Sum of the Prices Is Less Than or Equal to K
maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k
"""
You are given an integer k and an integer x.
Consider s is the 1-indexed binary representation of an integer num. The price of a number num is the number of i's such that i % x == 0 and s[i] is a set bit.
Return the greatest integer num such that the sum of prices of all numbers from 1 to num is less than or equal to k.
Note:

In the binary representation of a number set bit is a bit of value 1.
The binary representation of a number will be indexed from right to left. For example, if s == 11100, s[4] == 1 and s[2] == 0.


Example 1:

Input: k = 9, x = 1
Output: 6
Explanation: The numbers 1, 2, 3, 4, 5, and 6 can be written in binary representation as "1", "10", "11", "100", "101", and "110" respectively.
Since x is equal to 1, the price of each number is the number of its set bits.
The number of set bits in these numbers is 9. So the sum of the prices of the first 6 numbers is 9.
So the answer is 6.
Example 2:

Input: k = 7, x = 2
Output: 9
Explanation: Since x is equal to 2, we should just check eventh bits.
The second bit of binary representation of numbers 2 and 3 is a set bit. So the sum of their prices is 2.
The second bit of binary representation of numbers 6 and 7 is a set bit. So the sum of their prices is 2.
The fourth bit of binary representation of numbers 8 and 9 is a set bit but their second bit is not. So the sum of their prices is 2.
Numbers 1, 4, and 5 don't have set bits in their eventh bits in their binary representation. So the sum of their prices is 0.
The second and the fourth bit of the binary representation of the number 10 are a set bit. So its price is 2.
The sum of the prices of the first 9 numbers is 6.
Because the sum of the prices of the first 10 numbers is 8, the answer is 9.

Constraints:

1 <= k <= 1015
1 <= x <= 8
"""
class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        
You are given an integer k and an integer x.
Consider s is the 1-indexed binary representation of an integer num. The price of a number num is the number of i's such that i % x == 0 and s[i] is a set bit.
Return the greatest integer num such that the sum of prices of all numbers from 1 to num is less than or equal to k.
Note:

In the binary representation of a number set bit is a bit of value 1.
The binary representation of a number will be indexed from right to left. For example, if s == 11100, s[4] == 1 and s[2] == 0.


Example 1:

Input: k = 9, x = 1
Output: 6
Explanation: The numbers 1, 2, 3, 4, 5, and 6 can be written in binary representation as "1", "10", "11", "100", "101", and "110" respectively.
Since x is equal to 1, the price of each number is the number of its set bits.
The number of set bits in these numbers is 9. So the sum of the prices of the first 6 numbers is 9.
So the answer is 6.
Example 2:

Input: k = 7, x = 2
Output: 9
Explanation: Since x is equal to 2, we should just check eventh bits.
The second bit of binary representation of numbers 2 and 3 is a set bit. So the sum of their prices is 2.
The second bit of binary representation of numbers 6 and 7 is a set bit. So the sum of their prices is 2.
The fourth bit of binary representation of numbers 8 and 9 is a set bit but their second bit is not. So the sum of their prices is 2.
Numbers 1, 4, and 5 don't have set bits in their eventh bits in their binary representation. So the sum of their prices is 0.
The second and the fourth bit of the binary representation of the number 10 are a set bit. So its price is 2.
The sum of the prices of the first 9 numbers is 6.
Because the sum of the prices of the first 10 numbers is 8, the answer is 9.

Constraints:

1 <= k <= 1015
1 <= x <= 8


Please complete the code below to solve above prblem:
```python
class Solution:
    def findMaximumNumber(self, k: int, x: int) -> int:
        
```

my_solution = Solution()

test_input = { "k": 9, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 6

test_input = { "k": 7, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 9

test_input = { "k": 19, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 50

test_input = { "k": 57, "x": 4 }
assert my_solution.findMaximumNumber(**test_input) == 120

test_input = { "k": 58, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 121

test_input = { "k": 60, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 187

test_input = { "k": 72, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 151

test_input = { "k": 81, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 176

test_input = { "k": 83, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 33

test_input = { "k": 83, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 210

test_input = { "k": 116, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 243

test_input = { "k": 157, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 316

test_input = { "k": 201, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 212

test_input = { "k": 268, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 555

test_input = { "k": 281, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 531

test_input = { "k": 283, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 274

test_input = { "k": 309, "x": 4 }
assert my_solution.findMaximumNumber(**test_input) == 364

test_input = { "k": 363, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 746

test_input = { "k": 409, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 220

test_input = { "k": 456, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 967

test_input = { "k": 466, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 365

test_input = { "k": 500, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 379

test_input = { "k": 513, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 148

test_input = { "k": 521, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 1160

test_input = { "k": 540, "x": 4 }
assert my_solution.findMaximumNumber(**test_input) == 571

test_input = { "k": 545, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 156

test_input = { "k": 579, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 165

test_input = { "k": 584, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 166

test_input = { "k": 589, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 427

test_input = { "k": 599, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 1206

test_input = { "k": 632, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 346

test_input = { "k": 692, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 481

test_input = { "k": 701, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 1404

test_input = { "k": 704, "x": 4 }
assert my_solution.findMaximumNumber(**test_input) == 727

test_input = { "k": 731, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 1498

test_input = { "k": 781, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 210

test_input = { "k": 782, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 1613

test_input = { "k": 808, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 1639

test_input = { "k": 814, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 1645

test_input = { "k": 818, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 218

test_input = { "k": 821, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 433

test_input = { "k": 829, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 1660

test_input = { "k": 865, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 1760

test_input = { "k": 874, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 1769

test_input = { "k": 879, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 230

test_input = { "k": 879, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 628

test_input = { "k": 898, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 1921

test_input = { "k": 902, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 653

test_input = { "k": 905, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 1928

test_input = { "k": 937, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 1960

test_input = { "k": 957, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 701

test_input = { "k": 973, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 247

test_input = { "k": 978, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 737

test_input = { "k": 991, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 1006

test_input = { "k": 1029, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 771

test_input = { "k": 1065, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2083

test_input = { "k": 1086, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 805

test_input = { "k": 1105, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 280

test_input = { "k": 1113, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 815

test_input = { "k": 1143, "x": 4 }
assert my_solution.findMaximumNumber(**test_input) == 1190

test_input = { "k": 1148, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 564

test_input = { "k": 1150, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 2301

test_input = { "k": 1156, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 835

test_input = { "k": 1171, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 2386

test_input = { "k": 1172, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 297

test_input = { "k": 1227, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 2506

test_input = { "k": 1236, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 2515

test_input = { "k": 1270, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 1525

test_input = { "k": 1274, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2220

test_input = { "k": 1281, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2223

test_input = { "k": 1282, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2224

test_input = { "k": 1288, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 1543

test_input = { "k": 1376, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2287

test_input = { "k": 1393, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 2800

test_input = { "k": 1415, "x": 4 }
assert my_solution.findMaximumNumber(**test_input) == 1454

test_input = { "k": 1446, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 2917

test_input = { "k": 1459, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 358

test_input = { "k": 1520, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 1017

test_input = { "k": 1539, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2400

test_input = { "k": 1545, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3144

test_input = { "k": 1573, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 1732

test_input = { "k": 1588, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 3251

test_input = { "k": 1590, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3189

test_input = { "k": 1617, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3280

test_input = { "k": 1633, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2463

test_input = { "k": 1634, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3297

test_input = { "k": 1687, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 741

test_input = { "k": 1731, "x": 6 }
assert my_solution.findMaximumNumber(**test_input) == 2528

test_input = { "k": 1750, "x": 5 }
assert my_solution.findMaximumNumber(**test_input) == 1850

test_input = { "k": 1751, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3542

test_input = { "k": 1760, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 3551

test_input = { "k": 1782, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 3573

test_input = { "k": 1787, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 766

test_input = { "k": 1851, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 797

test_input = { "k": 1856, "x": 2 }
assert my_solution.findMaximumNumber(**test_input) == 799

test_input = { "k": 1874, "x": 8 }
assert my_solution.findMaximumNumber(**test_input) == 3793

test_input = { "k": 1893, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3812

test_input = { "k": 1900, "x": 1 }
assert my_solution.findMaximumNumber(**test_input) == 444

test_input = { "k": 1900, "x": 7 }
assert my_solution.findMaximumNumber(**test_input) == 3819

test_input = { "k": 1902, "x": 3 }
assert my_solution.findMaximumNumber(**test_input) == 1336