Java Recursive solution Time/Space Complexity O(logN)


  • 0
    F
    import java.util.*;
    
    public class Solution {
    
        static long[] x = new long[30];    // all valid numbers with ith digit to be 1.
        static long[] sums = new long[30];  // all valid numbers with #digits  <= i
    
        static {
            x[0] = 1;
            x[1] = 1;
            sums[0] = 1;
            sums[1] = 2;
            for(int w = 2;  w < x.length; w++){
                x[w] = sums[w-2];
                sums[w] = x[w] + sums[w-1];
            }
        }
    
    // # of valid numbers <= the first ind digits of a;
        private long aux(int[] a, int ind){
            if(ind < 0) return 1;
            if(ind == 0) return a[ind] == 0 ? 1 : 2;
            return a[ind] == 0 ? aux(a, ind - 1) : (sums[ind] + (a[ind-1] == 0? aux(a, ind - 2) : sums[ind-1]));
        }
    
        public int findIntegers(int num) {
            List<Integer> list = new ArrayList<>();
            while(num != 0){
                list.add(num%2);
                num/=2;
            }
            int[] a = new int[list.size()];
            for(int i = 0; i < list.size(); i++){
                a[i] = list.get(i);
            }
            return (int)aux(a, a.length-1);
        }
    }
    

Log in to reply
 

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