Java DP solution


  • 0
    S
        public int findIntegers(int num) {
            if (num < 0)
                return 0;
    
            return num - dp(num) + 1;
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        
        // get count of number with consecutive 1s
        public int dp(int num) {
            if (num < 3)
                return 0;
            Integer count = map.get(num);
            if (count != null)
                return count;
            int i = 31;
            while (i > 0 && ((1 << i) & num) == 0)
                i--;
            if (i <= 0)
                return 0;
              
            int next, result;  
            if ((1 << (i - 1) & num) > 0) {
                next = num - (1 << i) - (1 << (i-1));
                result = next + 1 + dp(num - next - 1);
            } else {
                next = num - (1 << i);
                result = dp(next) + dp((1 << i) - 1);
            }
            map.put(num, result);
            return result;
        }
    }

Log in to reply
 

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