Day1CountingBitsLC338.java

packageLeetcodeDaily.March2022;

importjava.util.Arrays;

publicclassDay1CountingBitsLC338 {

// O(N) time | O(N) space
publicstaticint[] countBits(intn) {

int[] countOfOnes = newint[n + 1];
countOfOnes[0] = 0;

for (inti = 1; i <= n; i++) {

if (i % 2 == 0) {
// for even number, LSB will be zero, so doing right shift of number by 1 bit
// will not lose set one bit(1)
countOfOnes[i] = countOfOnes[i / 2];
 } else {
// for odd number, LSB will always be one, so doing right shift of number by 1
// bit will also lose 1 bit
countOfOnes[i] = 1 + countOfOnes[i / 2];
 }
 }

returncountOfOnes;
 }

publicstaticvoidmain(String[] args) {
System.out.println(Arrays.toString(countBits(15)));
 }

}