The trick here is to name the state correctly, then let the implementation follow. For 868. Binary Gap, the solution in this repository is mainly a straightforward implementation solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: straightforward implementation.
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are binaryGap.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(logN). Note that logN is the number of digits in the binary representation of N.
- Space: O(logN), the space used by A.
Guide
C++ Solution
Your submission
The accepted solution
01/**
02Given a positive integer N, find and return the longest distance between two consecutive 1's in the binary representation of N.
03If there aren't two consecutive 1's, return 0.
04
05Example 1:
06
07Input: 22
08Output: 2
09Explanation:
1022 in binary is 0b10110.
11In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
12The first consecutive pair of 1's have distance 2.
13The second consecutive pair of 1's have distance 1.
14The answer is the largest of these two distances, which is 2.
15Example 2:
16
17Input: 5
18Output: 2
19Explanation:
205 in binary is 0b101.
21Example 3:
22
23Input: 6
24Output: 1
25Explanation:
266 in binary is 0b110.
27Example 4:
28
29Input: 8
30Output: 0
31Explanation:
328 in binary is 0b1000.
33There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.
34**/
35
36/**
37Complexity Analysis
38
39Time Complexity: O(logN). Note that logN is the number of digits in the binary representation of N.
40
41Space Complexity: O(logN), the space used by A.
42**/
43
44//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Binary Gap.
45//Memory Usage: 9.8 MB, less than 11.29% of C++ online submissions for Binary Gap.
46class Solution {
47public:
48 int binaryGap(int N) {
49 vector<int> onePos;
50 int digit = 0;
51 int ans = 0;
52
53 while(N!=0){
54 if(N%2==1){
55 onePos.push_back(digit);
56 }
57 N >>= 1;
58 digit++;
59 }
60
61 if(onePos.size()<2){
62 return 0;
63 }
64
65 for(int i = 1; i < onePos.size(); i++){
66 ans = max(onePos[i] - onePos[i-1], ans);
67 }
68
69 return ans;
70 }
71};
72
73/**
74Approach 2: One Pass
75Intuition
76
77In Approach 1, we created an array A of indices i for which N had the ith bit set.
78
79Since we only care about consecutive values of this array A, we don't need to store the whole array. We only need to remember the last value seen.
80
81Algorithm
82
83We'll store last, the last value added to the virtual array A. If N has the ith bit set, a candidate answer is i - last, and then the new last value added to A would be last = i.
84**/
85
86/**
87Complexity Analysis
88
89Time Complexity: O(logN). Note that logN is the number of digits in the binary representation of N.
90
91Space Complexity: O(1).
92**/
93
94//Runtime: 4 ms, faster than 100.00% of C++ online submissions for Binary Gap.
95//Memory Usage: 9.7 MB, less than 48.39% of C++ online submissions for Binary Gap.
96
97/**
98class Solution {
99public:
100 int binaryGap(int N) {
101 int digit = 0;
102 int ans = 0;
103 int last = -1;
104
105 while(N!=0){
106 if(N%2==1){
107 if(last>=0){
108 ans = max(digit - last, ans);
109 }
110 last = digit;
111 }
112 N >>= 1;
113 digit++;
114 }
115
116 return ans;
117 }
118};
119**/Cost