ConsecutiveOnes | Topcoder Archive

Problem Statement

You are given a long n. You are also given an int k that is a positive integer between 1 and 50, inclusive. Find and return the smallest m such that:

m is greater than or equal to n
the binary representation of m contains (at least) k consecutive ones

Definition

Class:: ConsecutiveOnes
Method:: get
Parameters:: long, int
Returns:: long
Method signature:: long get(long n, int k)
(be sure your method is public)

Constraints

n will be beween 0 and 2^50 - 1, inclusive.
k will be between 1 and 50, inclusive.

Examples

```
1
```
```
2
```
```
Returns: 3
```
We want the smallest integer that is at least 1 and contains 2 consecutive ones in binary. Clearly the smallest such integer is 3.
```
5
```
```
2
```
```
Returns: 6
```
The binary representation of the number 5 is 101, which does not contain two consecutive ones. The next integer is 6, which is 110 in binary. As this does contain two consecutive ones, the correct return value is 6.
```
7
```
```
2
```
```
Returns: 7
```

364269800189924

Returns: 364273356242943

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.