# Java Memoized DP Solution

• ``````public int findIntegers(int num) {
return findIntegers(num, new HashMap<>());
}

public int findIntegers(int num, Map<Integer, Integer> memo) {
if (num <= 2) return num + 1; // base case
if (memo.containsKey(num)) return memo.get(num); // check if this result has already been computed

int msb = 31 - Integer.numberOfLeadingZeros(num); // retrieve index of most significant bit
int subNum = (1 << msb) - 1, subNum2 = ~(1 << msb) & num;
if (subNum2 >= 1 << msb - 1) subNum2 = subNum >> 1;
int result = findIntegers(subNum, memo) + findIntegers(subNum2, memo);

memo.put(num, result); // add result to memo
return result;
}
``````

• can you give us some explanation here? What do these three lines do?

``````    int subNum = (1 << msb) - 1, subNum2 = ~(1 << msb) & num;
if (subNum2 >= 1 << msb - 1) subNum2 = subNum >> 1;
int result = findIntegers(subNum, memo) + findIntegers(subNum2, memo);
``````

• @tiandiao123 My equivalent approach which is a little more self-explanatory

``````    int res = 0;
int x = Integer.highestOneBit(num); // e.g. highestOneBit(1011) = 1000
res += findIntegers(x - 1); // e.g. x = 1000, x - 1 = 0111.
int y = Integer.highestOneBit(num - x);
if (y << 1 == x) res += findIntegers(y - 1);
else res += findIntegers(num - x);
m.put(num, res);
return res;
``````

A few examples:
f(110010) = f(011111) + f(001111)
f(101010) = f(011111) + f(001010)

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