一個二進制正整數 N,
舉例來說 9 二進制為 1001 含有二進制的間隙長度為 2,
數字 525 二進制為 1000010001 含有兩種二進制間隙分別為 4 跟 3,
數字 20 二進制為 10100 二進制間隙為 1,
數字 15 二進制為 1111 則沒有二進制間隙。
寫一個 function:
class Solution { public int solution(int N); }
給一個正整數 N ,返回最大的二進制間隙,如果沒有,則返回 0
舉例來說 N = 1041 則 function 返回 5,因為 N 的二進制為 10000010001,則最大的間隙為 5。
條件:
- N的範圍必須是 1.., 2, 147, 483, 647
 
複雜度:
- 最糟的時間複雜度為 O(log(N))
 
- 最糟的空間複雜度為 O(1) (不含 input 的參數)
 
Java 程式碼
// you can also use imports, for example:
class Solution {
    public int solution(int X, int[] A) {
        // write your code in Java SE 8
        HashSet<Integer> set = new HashSet<Integer>();
        for(int i = 0;i<A.length;i++){
            if(A[i]<=X){set.add(A[i]);}
           
           if(set.size() == X){
               return i;
           }
        }
        return -1;
    }
}
分數共拿 80%,
訂正版
需考慮 1000 這種後面沒 1 的不成立二進制間隙,
1001000 也會變成  3,須把後面不成立間隙的部分 000 移除。
Java 程式碼
// you can also use imports, for example:
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
    public int solution(int[] A) {
        // write your code in Java SE 8
         // write your code in Java SE 8
        Arrays.sort(A);
        if(A.length == 3){
            return A[0] * A[1] *A[2];
        }
      
        int N = A.length;
        int result = 0;
        if(A[0] * A[1] > 0 && A[0] < 0){
            result = Math.max(A[0] * A[1] *A[N-1],A[N - 1] * A[N - 2] *A[N - 3]);
        }else{
            result =A[N - 1] * A[N - 2] *A[N - 3];
        }
        
        return result;
    }
}
分數共拿 100%
任何問題歡迎交流討論,一起學習!
更多面試相關
⇒ 
[Codility] 面試寫題目經驗感想
感謝相關連結
https://www.codility.com/