BitOrder | Topcoder Archive

Problem Statement

Sort all the integers between first and last, inclusive, using the number of 1's in their binary representations. Integers with fewer 1's must come before integers with more 1's. If two integers have the same number of 1's, the smaller integer must come first. Return the k-th (0-based) integer in the sorted list.

Definition

Class:: BitOrder
Method:: kthElement
Parameters:: int, int, int
Returns:: int
Method signature:: int kthElement(int first, int last, int k)
(be sure your method is public)

Constraints

first will be between 1 and 10^9, inclusive.
last will be between first and 10^9, inclusive.
k will be between 0 and (last - first), inclusive.

Examples

```
1
```
```
10
```
```
3
```
```
Returns: 8
```
Sorting all integers between 1 and 10, inclusive, produces the following sequence: {1, 2, 4, 8, 3, 5, 6, 9, 10, 7}
```
1
```
```
10
```
```
4
```
```
Returns: 3
```
```
11
```
```
1024
```
```
1013
```
```
Returns: 1023
```
```
5577
```
```
5577
```
```
0
```
```
Returns: 5577
```
```
1
```
```
1000000000
```
```
20
```
```
Returns: 1048576
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.