/*
https://www.codewars.com/kata/twice-linear/train/java
*/

public class Main {
    public static int dblLinear (int n) {
        LinkedList<Integer> sequence = new LinkedList<>();
        sequence.add(1);
        for (int i = 0; i < n; i++) {
            int x = sequence.get(i);
            int y = x * 2 + 1;
            int z = x * 3 +1;

            addToSortedList(sequence, y);
            addToSortedList(sequence, z);
        }

//        System.out.println(sequence);
//        // check for duplicates
//        for (int i = 0; i < sequence.size() - 1; i++) {
//            if (sequence.get(i).equals(sequence.get(i + 1))) {
//                System.out.println("ERROR FOUND: " + sequence.get(i));
//            }
//        }

        return sequence.get(n);
    }

    private static <T extends Comparable> int addToSortedList (LinkedList<T> list, T val) {
        if (list.size() == 0) {
            list.add(val);
            return 0;
        }

        if (val.compareTo(list.get(list.size()-1)) == 1) {
            list.add(val);
            return list.size() - 1;
        }

        int lowerBound = 0;
        int upperBound = list.size()-1;
        while (true) {
            if (upperBound <= lowerBound) {  // have we found the proper position yet?
                if (val.compareTo(list.get(lowerBound)) == 1) {
                    list.add(lowerBound + 1, val);
                    return lowerBound + 1;
                }
                else if (val.compareTo(list.get(lowerBound)) == -1) {
                    list.add(lowerBound, val);
                    return lowerBound;
                }
                else {
//                  list.add(lowerBound, val);  // ! uncomment if you want to add DUPLICATES to the list !
                    return lowerBound;
                }
            }
            // compare value to the middle element of the [lowerBound, upperBound] range
            int midPoint = lowerBound + (upperBound - lowerBound) / 2;
            int compResult = val.compareTo(list.get(midPoint));
            if (compResult == 0) {          // check if value equals list[midPoint]
//              list.add(midPoint, val);    // ! uncomment if you want to add DUPLICATES to the list !
                return midPoint;            // !

            }
            else if (compResult == -1) {    // check if value is lesser than list[midPoint]
                upperBound = midPoint - 1;
            }
            else {                          // check if value is greater than list[midPoint]
                lowerBound = midPoint + 1;
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(dblLinear(10));          // should be 22
        System.out.println(dblLinear(20));          // should be 57
        System.out.println(dblLinear(30));          // should be 91
        System.out.println(dblLinear(50));          // should be 175
    }
}