ConsecutiveOnes
SRM 711 · 2017-02-20 · by Arterm
SRM 711 · 2017-02-20 · by Arterm · Brute Force, Dynamic Programming, Simple Math
Problem Statement
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
Constraints
- n will be beween 0 and 2^50 - 1, inclusive.
- k will be between 1 and 50, inclusive.
Examples
0)
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.
1)
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.
2)
7 2 Returns: 7
3)
1023 11 Returns: 2047
4)
364269800189924 33 Returns: 364273356242943
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ConsecutiveOnes with a public method long long get(long long n, int k) · 56 test cases · 2 s / 256 MB per case