#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
std::vector<bool> to_binary(int num)
{
std::vector<bool> binary;
while(num != 0)
{
binary.emplace_back(num % 2 != 0);
num /= 2;
}
return binary;
}
int findlargestGap(int num)
{
int largest_gap = 0;
auto binary = to_binary(num);
auto it = binary.begin();
const auto it_end = binary.end();
while(it != it_end)
{
auto current_true = std::find(it, it_end, true);
if(current_true == it_end)
break;
auto next_true = std::find(current_true+1, it_end, true);
if(next_true == it_end)
break;
const auto d = std::distance(current_true, next_true) - 1;
largest_gap = std::max(largest_gap, static_cast<int>(d));
it = next_true;
}
return largest_gap;
}
int main(int argc, char** argv)
{
std::cout << "largest gap for 9: " << findlargestGap(9) << '\n';
std::cout << "largest gap for 529: " << findlargestGap(529) << '\n';
std::cout << "largest gap for 20: " << findlargestGap(20) << '\n';
std::cout << "largest gap for 15: " << findlargestGap(15) << '\n';
std::cout << "largest gap for 32: " << findlargestGap(32) << '\n';
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bnVtZXJpYz4KI2luY2x1ZGUgPHZlY3Rvcj4KCnN0ZDo6dmVjdG9yPGJvb2w+IHRvX2JpbmFyeShpbnQgbnVtKQp7CiAgc3RkOjp2ZWN0b3I8Ym9vbD4gYmluYXJ5OwogIHdoaWxlKG51bSAhPSAwKQogIHsKICAgIGJpbmFyeS5lbXBsYWNlX2JhY2sobnVtICUgMiAhPSAwKTsKICAgIG51bSAvPSAyOwogIH0KICByZXR1cm4gYmluYXJ5Owp9CgppbnQgZmluZGxhcmdlc3RHYXAoaW50IG51bSkKewogIGludCBsYXJnZXN0X2dhcCA9IDA7CiAgYXV0byBiaW5hcnkgICAgICAgPSB0b19iaW5hcnkobnVtKTsKICBhdXRvICAgICAgIGl0ICAgICA9IGJpbmFyeS5iZWdpbigpOwogIGNvbnN0IGF1dG8gaXRfZW5kID0gYmluYXJ5LmVuZCgpOwogIHdoaWxlKGl0ICE9IGl0X2VuZCkKICB7CiAgICBhdXRvIGN1cnJlbnRfdHJ1ZSA9IHN0ZDo6ZmluZChpdCwgaXRfZW5kLCB0cnVlKTsKICAgIGlmKGN1cnJlbnRfdHJ1ZSA9PSBpdF9lbmQpCiAgICAgIGJyZWFrOwoKICAgIGF1dG8gbmV4dF90cnVlID0gc3RkOjpmaW5kKGN1cnJlbnRfdHJ1ZSsxLCBpdF9lbmQsIHRydWUpOwogICAgaWYobmV4dF90cnVlID09IGl0X2VuZCkKICAgICAgYnJlYWs7CgogICAgY29uc3QgYXV0byBkID0gc3RkOjpkaXN0YW5jZShjdXJyZW50X3RydWUsIG5leHRfdHJ1ZSkgLSAxOwogICAgbGFyZ2VzdF9nYXAgPSBzdGQ6Om1heChsYXJnZXN0X2dhcCwgc3RhdGljX2Nhc3Q8aW50PihkKSk7CgogICAgaXQgPSBuZXh0X3RydWU7CiAgfQoKICByZXR1cm4gbGFyZ2VzdF9nYXA7Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyKiogYXJndikKewogIHN0ZDo6Y291dCA8PCAibGFyZ2VzdCBnYXAgZm9yIDk6ICIgICA8PCBmaW5kbGFyZ2VzdEdhcCg5KSA8PCAnXG4nOwogIHN0ZDo6Y291dCA8PCAibGFyZ2VzdCBnYXAgZm9yIDUyOTogIiA8PCBmaW5kbGFyZ2VzdEdhcCg1MjkpIDw8ICdcbic7CiAgc3RkOjpjb3V0IDw8ICJsYXJnZXN0IGdhcCBmb3IgMjA6ICIgIDw8IGZpbmRsYXJnZXN0R2FwKDIwKSA8PCAnXG4nOwogIHN0ZDo6Y291dCA8PCAibGFyZ2VzdCBnYXAgZm9yIDE1OiAiICA8PCBmaW5kbGFyZ2VzdEdhcCgxNSkgPDwgJ1xuJzsKICBzdGQ6OmNvdXQgPDwgImxhcmdlc3QgZ2FwIGZvciAzMjogIiAgPDwgZmluZGxhcmdlc3RHYXAoMzIpIDw8ICdcbic7Cn0K