mirror of
https://github.com/Manoj-HV30/dsa-competitive-programming.git
synced 2026-05-16 19:35:22 +00:00
19 lines
606 B
C++
19 lines
606 B
C++
class Solution{
|
|
public :
|
|
int binaryGap(int n){
|
|
int last = -1;
|
|
int ans =0;
|
|
for(int i =0;i<32;i++){
|
|
if(n>>i & 1){
|
|
if(last!=-1)
|
|
ans = max(ans, i-last);
|
|
last = i;
|
|
}
|
|
}
|
|
return ans;
|
|
}
|
|
};
|
|
//We'll store last, the index of the last set bit encountered. If n has the ith bit set, answer is i - last, and then the new last value would be last = i.
|
|
//TC : o(logn) , logn is the number of digits in the binary representation of n
|
|
//SC : o(1)
|