Find 1’s how many times repeated in bits of given number

Problem:
Given a non-negative integer number num. For every number i in the range 0<i<num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num=5, you should return [0,1,1,2,1,2].

1. Native Solution:
We can simply count the bits for each number like below,

package com.algorithm.bitcount;

public class NativeSolution {

    public static void main(String[] args) {
        for (int i : countBits(5)) {
            System.out.println(i);
        }
    }

    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        for (int i = 0; i <= num; i++) {
            result[i] = countEach(i);
        }
        return result;
    }

    public static int countEach(int num) {
        int result = 0;
        while (num != 0) {
            if (num % 2 == 1) {
                result++;
            }
            num = num / 2;
        }
        return result;
    }
}

2. Improved Solution:
For number 2(10), 4(100),6(1000),8(10000), etc the number of 1’s is 1. Any other can be converted to be 2m+x. For example, 9=8+1,10=8+2. The number of 1’s for any other number is 1+ # of 1’s in x.

package com.algorithm.bitcount;

public class ImprovedSolution {

    public static void main(String[] args) {
        for (int i : countBits(5)) {
            System.out.println(i);
        }
    }

    public static int[] countBits(int num) {
        int[] result = new int[num + 1];
        int p = 1; // p tracks the index for number x
        int pow = 1;
        for (int i = 1; i <= num; i++) {
            if (i == pow) {
                result[i] = 1;
                pow <<= 1;
                p = 1;
            } else {
                result[i] = result[p] + 1;
                p++;
            }
        }
        return result;
    }
}

Maximum product of word lengths in Java

Given string array words, find the maximum value of length(word[i])*length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.
 
package com.algorithm.length;

public class WordsLength {

    public static void main(String[] args) {
        String str[] = {"abc","def"};
        System.out.println(maxProduct(str));
    }

    public static int maxProduct(String[] words) {
        if(words==null || words.length==0)
            return 0;
        int[] arr = new int[words.length];
        for(int i=0; i<words.length; i++){
            for(int j=0; j<words[i].length(); j++){
                char c = words[i].charAt(j);
                arr[i] |= (1 << (c-'a'));
            }
        }
        int result = 0;
        for(int i=0; i<words.length; i++){
            for(int j=i+1; j<words.length; j++){
                if((arr[i] & arr[j]) == 0){
                    result = Math.max(result, words[i].length()*words[j].length());
                }
            }
        }
        return result;
    }
}

Test Cases:
1. We have passed two words are “abc” and “def”. Those words don’t have any common letters. So, the output will be 9.
2. If we pass any words which have any common letters, the program has to return 0.

Gray Code or Binary numeral system in Java

The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is: 00 – 0 01 – 1 11 – 3 10 – 2.

The solution in Java:

package com.algorithm.graycode;

import java.util.ArrayList;
import java.util.List;

public class BinaryCodeSystem {

    public static void main(String[] args) {
        grayCode(2).forEach(i->System.out.println(i));
    }

    public static List<Integer> grayCode(int n) {
        if (n == 0) {
            List<Integer> result = new ArrayList<Integer>();
            result.add(0);
            return result;
        }
        List<Integer> result = grayCode(n - 1);
        int numToAdd = 1 << (n - 1);
        for (int i = result.size() - 1; i >= 0; i--) {
            result.add(numToAdd + result.get(i));
        }
        return result;
    }
}