package prac;

import java.util.Arrays;
import java.util.stream.IntStream;

public class question04_triangular {
    public static void main(String[] args){

//      int[] testA = new int[]{10, 2, 5, 18, 20};
//      int[] testA = new int[]{10, 50, 5, 1};
//      int[] testA = new int[]{1, 3, 9, 10, 15, 50 ,60, 62, 80};
//      int[] testA = new int[]{1, 3, 50 ,60, 62, 80};
//      int[] testA = new int[]{1, 3, 9, 10, 15, 15, 50, 50,60 , 62, 80};
//      int[] testA = new int[]{1, 2, 5, 8, 10, 20};
        int[] testA = new int[]{5,3,3};
//      int[] testA = new int[]{5,3,1};
//      int[] testA = new int[]{5,3,1,5,7};
//      int[] testA = new int[]{1, 1, 2, 3, 5};
//      int[] testA = new int[0];
//      int[] testA = new int[]{-100, 5, 4, 3};
//      int[] testA = new int[]{10, -2147483648, -2147483648};

        question04_triangular question = new question04_triangular();
        System.out.println("result: " + question.solution(testA));
    }

    // O(n(log n) + n*((log n)**2))
    public int solution(int[] A) {
        int result = 0;

        // 先sorting O(n(log n))
        Arrays.sort(A);

        // 搜尋: O(n((log n)**2))
        int length = A.length;
        // 第一層: O(n)
        for (int i = length-1; i > 1; i--){
            int max_num_index = i;
//          int initial_mid = (curr_max + 1) / 2;

            int second_num_index = (max_num_index + 1) / 2; // 若有兩個數在中間,則取左邊那個
            int curr_max_val = A[max_num_index];

            // 最大值若為零或負值，則不用再比
            if (curr_max_val <= 0){
                break;
            }

            // 第二層: O(log(n))
            while(result == 0 && second_num_index < max_num_index){
                int second_num_val = A[second_num_index];

                if (second_num_val > 0){
                    // 若有比此gap大的數,則代表找到一個三角形了
                    result = checkIfAryHasElmtBiggerThanTheGap(A, max_num_index,second_num_index);
                    if (result != 0){
                        break;
                    }
                }

                second_num_index = (second_num_index + max_num_index + 1)/2;

            }// end of while
            if (result != 0){
                break;
            }
        }// end of for

        return result;
    }

    private int checkIfAryHasElmtBiggerThanTheGap(int[] A, int max_num_index, int second_num_index){

        int gap = A[max_num_index] - A[second_num_index];
        int low = 0;
        int high = max_num_index - 1; // 不要再找自己 (因為其為目前挑選的第一個數字)

        // 第三層: O(log(n))
        while (low <= high) {
            int mid = (low + high) / 2;
            if (A[mid] > gap && mid != second_num_index){ // 不要再找中間數 (因為其為目前挑選的第二個數字)
                // 若走進此區塊，則表示我們找到了第三個數字
                // 在此定義: (最大數 - 第二個數字) = k;
                // 證明若(第三個數字) > k, 則三角形成立:
                //
                // 有鑑於 (第二個數字 + k = 最大數 ),
                // 由 (第三個數字) > k,
                // 可推得 (第二個數字 + (第三個數字)) >  (第二個數字 + k) == 最大數)
                // 故可得 (第二個數字 + (第三個數字)) > 最大數
                // 即代表 最小的兩個數相加 > 最大數
                //
                // 即可證此三數可以組成一個三角形
                return 1;
            }else{
                low = mid + 1;
            }
        }// end of while

        return 0;
    }
}