Problem
Given a positive integer N
, find and return the longest distance between two consecutive 1’s in the binary representation of N
.
If there aren’t two consecutive 1’s, return 0.
Example 1:
Input: 22
Output: 2
Explanation:
22 in binary is 0b10110.
In the binary representation of 22, there are three ones, and two consecutive pairs of 1's.
The first consecutive pair of 1's have distance 2.
The second consecutive pair of 1's have distance 1.
The answer is the largest of these two distances, which is 2.
Example 2:
Input: 5 Output: 2 Explanation: 5 in binary is 0b101.
Example 3:
Input: 6 Output: 1 Explanation: 6 in binary is 0b110.
Example 4:
Input: 8 Output: 0 Explanation: 8 in binary is 0b1000. There aren't any consecutive pairs of 1's in the binary representation of 8, so we return 0.\
Note:
1 <= N <= 10^9
Solution: Bit
Time complexity: O(logN)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 4 ms class Solution { public: int binaryGap(int N) { int l = -1; int ans = 0; for (int i = 0; i < 31; ++i) if (N & (1 << i)) { if (l >= 0) ans = max(ans, i - l); l = i; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment