868. Binary Gap

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int binaryGap(int n) {
        // if n is 2-power return false;
        if( (n&(n-1))==0) return false;
        int gap = 0;
        int i = 0, j=0;
        bool flag = false;
        while(n){
            if(n&1){
                if(flag==false){
                    // 第一次
                    flag = true;
                }
                else{
                    gap = max(gap , i-j);
                }
                j =i ;
            }
            i++;
            n>>=1;
        }
        return gap;
    }
};

analysis

  • time complexity O(logn)
  • space complexity O(1)