Skip to content

Instantly share code, notes, and snippets.

@codyhex
Created September 30, 2017 18:38
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save codyhex/5ea5485434bf3b9e73d6f59cd230bd6a to your computer and use it in GitHub Desktop.
checking the max consecutive one sequence in a bitmap array(number)
// https://www.hackerrank.com/challenges/30-binary-numbers/problem
using namespace std;
int main(){
int n;
cin >> n;
int count = 0;
int old = 0;
// one stupid way is to calculate what is the highest bit rank that a 1 is at.
// for example, a number 8 will give you log(8) = 3, and +1 (for the zero bit)
// so in total you need to check the number 4 times.
// int bit = int(floor(log2(n))) + 1;
// int checker = 1;
// for(int i = 0; i <= bit; ++i) {
// if ((n & checker) > 0) {
// count++;
// } else {
// old = max(old, count);
// count = 0;
// }
// checker = checker << 1;
// }
// A second method is simply shift the number right and bit and with lowest 0000 0001
// Program exits when there is no 1 bits in the number.
while(n > 0) {
if ((n & 1) > 0) {
count++;
} else {
old = max(old, count);
count = 0;
}
n = n >> 1;
}
// This is very important that you update the results
// because the while operation may keep adding the count when the highest bit is 1
// and exit from there without updating the old max consective value.
int result = max(old, count);
cout << result;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment