3007. Maximum Number That Sum of the Prices Is Less Than or Equal to K Medium
1/**
2 * [3007] Maximum Number That Sum of the Prices Is Less Than or Equal to K
3 *
4 * You are given an integer k and an integer x. The price of a number num is calculated by the count of <span data-keyword="set-bit">set bits</span> 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.
5 * <table border="1">
6 * <tbody>
7 * <tr>
8 * <th>x</th>
9 * <th>num</th>
10 * <th>Binary Representation</th>
11 * <th>Price</th>
12 * </tr>
13 * <tr>
14 * <td>1</td>
15 * <td>13</td>
16 * <td><u>0</u><u>0</u><u>0</u><u>0</u><u>0</u><u>1</u><u>1</u><u>0</u><u>1</u></td>
17 * <td>3</td>
18 * </tr>
19 * <tr>
20 * <td>2</td>
21 * <td>13</td>
22 * <td>0<u>0</u>0<u>0</u>0<u>1</u>1<u>0</u>1</td>
23 * <td>1</td>
24 * </tr>
25 * <tr>
26 * <td>2</td>
27 * <td>233</td>
28 * <td>0<u>1</u>1<u>1</u>0<u>1</u>0<u>0</u>1</td>
29 * <td>3</td>
30 * </tr>
31 * <tr>
32 * <td>3</td>
33 * <td>13</td>
34 * <td><u>0</u>00<u>0</u>01<u>1</u>01</td>
35 * <td>1</td>
36 * </tr>
37 * <tr>
38 * <td>3</td>
39 * <td>362</td>
40 * <td><u>1</u>01<u>1</u>01<u>0</u>10</td>
41 * <td>2</td>
42 * </tr>
43 * </tbody>
44 * </table>
45 * 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.
46 * Return the greatest cheap number.
47 *
48 * <strong class="example">Example 1:
49 * <div class="example-block">
50 * Input: <span class="example-io">k = 9, x = 1</span>
51 * Output: <span class="example-io">6</span>
52 * Explanation:
53 * As shown in the table below, 6 is the greatest cheap number.
54 * <table border="1">
55 * <tbody>
56 * <tr>
57 * <th>x</th>
58 * <th>num</th>
59 * <th>Binary Representation</th>
60 * <th>Price</th>
61 * <th>Accumulated Price</th>
62 * </tr>
63 * <tr>
64 * <td>1</td>
65 * <td>1</td>
66 * <td><u>0</u><u>0</u><u>1</u></td>
67 * <td>1</td>
68 * <td>1</td>
69 * </tr>
70 * <tr>
71 * <td>1</td>
72 * <td>2</td>
73 * <td><u>0</u><u>1</u><u>0</u></td>
74 * <td>1</td>
75 * <td>2</td>
76 * </tr>
77 * <tr>
78 * <td>1</td>
79 * <td>3</td>
80 * <td><u>0</u><u>1</u><u>1</u></td>
81 * <td>2</td>
82 * <td>4</td>
83 * </tr>
84 * <tr>
85 * <td>1</td>
86 * <td>4</td>
87 * <td><u>1</u><u>0</u><u>0</u></td>
88 * <td>1</td>
89 * <td>5</td>
90 * </tr>
91 * <tr>
92 * <td>1</td>
93 * <td>5</td>
94 * <td><u>1</u><u>0</u><u>1</u></td>
95 * <td>2</td>
96 * <td>7</td>
97 * </tr>
98 * <tr>
99 * <td>1</td>
100 * <td>6</td>
101 * <td><u>1</u><u>1</u><u>0</u></td>
102 * <td>2</td>
103 * <td>9</td>
104 * </tr>
105 * <tr>
106 * <td>1</td>
107 * <td>7</td>
108 * <td><u>1</u><u>1</u><u>1</u></td>
109 * <td>3</td>
110 * <td>12</td>
111 * </tr>
112 * </tbody>
113 * </table>
114 * </div>
115 * <strong class="example">Example 2:
116 * <div class="example-block">
117 * Input: <span class="example-io">k = 7, x = 2</span>
118 * Output: <span class="example-io">9</span>
119 * Explanation:
120 * As shown in the table below, 9 is the greatest cheap number.
121 * <table border="1">
122 * <tbody>
123 * <tr>
124 * <th>x</th>
125 * <th>num</th>
126 * <th>Binary Representation</th>
127 * <th>Price</th>
128 * <th>Accumulated Price</th>
129 * </tr>
130 * <tr>
131 * <td>2</td>
132 * <td>1</td>
133 * <td><u>0</u>0<u>0</u>1</td>
134 * <td>0</td>
135 * <td>0</td>
136 * </tr>
137 * <tr>
138 * <td>2</td>
139 * <td>2</td>
140 * <td><u>0</u>0<u>1</u>0</td>
141 * <td>1</td>
142 * <td>1</td>
143 * </tr>
144 * <tr>
145 * <td>2</td>
146 * <td>3</td>
147 * <td><u>0</u>0<u>1</u>1</td>
148 * <td>1</td>
149 * <td>2</td>
150 * </tr>
151 * <tr>
152 * <td>2</td>
153 * <td>4</td>
154 * <td><u>0</u>1<u>0</u>0</td>
155 * <td>0</td>
156 * <td>2</td>
157 * </tr>
158 * <tr>
159 * <td>2</td>
160 * <td>5</td>
161 * <td><u>0</u>1<u>0</u>1</td>
162 * <td>0</td>
163 * <td>2</td>
164 * </tr>
165 * <tr>
166 * <td>2</td>
167 * <td>6</td>
168 * <td><u>0</u>1<u>1</u>0</td>
169 * <td>1</td>
170 * <td>3</td>
171 * </tr>
172 * <tr>
173 * <td>2</td>
174 * <td>7</td>
175 * <td><u>0</u>1<u>1</u>1</td>
176 * <td>1</td>
177 * <td>4</td>
178 * </tr>
179 * <tr>
180 * <td>2</td>
181 * <td>8</td>
182 * <td><u>1</u>0<u>0</u>0</td>
183 * <td>1</td>
184 * <td>5</td>
185 * </tr>
186 * <tr>
187 * <td>2</td>
188 * <td>9</td>
189 * <td><u>1</u>0<u>0</u>1</td>
190 * <td>1</td>
191 * <td>6</td>
192 * </tr>
193 * <tr>
194 * <td>2</td>
195 * <td>10</td>
196 * <td><u>1</u>0<u>1</u>0</td>
197 * <td>2</td>
198 * <td>8</td>
199 * </tr>
200 * </tbody>
201 * </table>
202 * </div>
203 *
204 * Constraints:
205 *
206 * 1 <= k <= 10^15
207 * 1 <= x <= 8
208 *
209 */
210pub struct Solution {}
211
212// problem: https://leetcode.com/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/
213// discuss: https://leetcode.com/problems/maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k/discuss/?currentPage=1&orderBy=most_votes&query=
214
215// submission codes start here
216
217impl Solution {
218 pub fn find_maximum_number(k: i64, x: i32) -> i64 {
219
220 }
221}
222
223// submission codes end
224
225#[cfg(test)]
226mod tests {
227 use super::*;
228
229 #[test]
230 fn test_3007() {
231 }
232}
233Back
© 2025 bowen.ge All Rights Reserved.