Short O(lg(n)) java solutions, recursive & iterative


  • 0
    T

    Recursive:

        public int findIntegers(int num) {
        // Fibonacci
        int[] oneone = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};
            if (num == 0) return 1;
            int leftmost = Integer.numberOfLeadingZeros(num);
    
            int bit = 1 << (30 - leftmost);
            if ((bit & num) > 0) return oneone[32 - leftmost];
            return oneone[31 - leftmost] + findIntegers(num - (1 << (31 - leftmost)));
        }
    

    Iterative:

        public int findIntegers(int num) {
        // Fibonacci
        int[] oneone = {1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578};
            int ans = 0;
            for (int bit = 1 << 30, i = 31; i > 0; bit >>= 1, i--) {
                if ((num & bit) == 0) continue;
                if ((num & (bit >> 1)) != 0) {
                    return ans + oneone[i];
                }
                ans += oneone[i - 1];
            }
            return ans + 1;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.