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;
    }
}

Advertisement

Implement pow(x,n) using Java

This is a great example to illustrate how to solve a problem during a technical interview. The first and second solution exceeds the time limit, the third and fourth are accepted.

1. Recursive Method:
In general, we next may think how to do it in O(logn). We have a relation that

Xn = X2(n/2)*X2(n/2)*X2(n)

package com.algorithm.pow;

//This class has the pow method to calculate pow of X with recursive
public class PowXN {

    public static void main(String[] args) {
        System.out.println(pow(5.0, 2));
    }

    public static double pow(double x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        int half = n / 2;
        int remainder = n % 2;
        if (n % 2 == 1 && x < 0 && n < 0)
            return -1 / (pow(-x, half) * pow(-x, half) * pow(-x, remainder));
        else if (n < 0)
            return 1 / (pow(x, -half) * pow(x, -half) * pow(x, -remainder));
        else
            return (pow(x, half) * pow(x, half) * pow(x, remainder));
    }
}

2. Accepted Solution:
The accepted solution is also recursive, but does division first. Time complexity is O(nlog(n)). The key part of solving this problem is the while loop.

package com.algorithm.pow;

/*PowAcceptedSolution class has the method to calculate the pow of X
with with better solution than the recursive way.*/
public class PowAcceptedSolution {

    public static void main(String[] args) {
        System.out.println(pow(6.0, 3));
    }

    public static double pow(double x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;

        int pn = n > 0 ? n : -n;// positive n
        int pn2 = pn;
        double px = x > 0 ? x : -x;// positive x
        double result = px;
// handle negative result
        if (x < 0 && n % 2 == 1)
            result = -result;
// handle negative power
        if (n < 0)
            result = 1 / result;
        int k = 1; // the key part of solving this problem
        while (pn / 2 > 0) {
            result = result * result;
            pn = pn / 2;
            k = k * 2;
        }
        result = result * pow(px, pn2 - k);
        return result;
    }
}

3. Best Solution:
This is the best and easy solution than the above two solutions.

package com.algorithm.pow;

public class PowBestSolution {

    public static void main(String[] args) {
        System.out.println(pow(6.0, 1));
    }

    public static double power(double x, int n) {
        if (n == 0)
            return 1;
        double v = power(x, n / 2);
        if (n % 2 == 0) {
            return v * v;
        } else {
            return v * v * x;
        }
    }

    public static double pow(double x, int n) {
        if (n < 0) {
            return 1 / power(x, -n);
        } else {
            return power(x, n);
        }
    }
}

Please let me know if you have any best solutions than the above mentioned.

Two Sum Problem in java

Problem:
Given an array of integers, find two numbers such that they add up to the specific  target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

For Example:
Input: number={2,7,11,15};
Output: Index1=0, Index2=1

Solution:

Using HashMap to store the target value

package com.algorithm.twosum;

import java.util.HashMap;

public class Solution {
	public static int[] twoSum(int[] numbers, int target) {
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int[] result = new int[2];
		for (int i = 0; i < numbers.length; i++) {
			if (map.containsKey(numbers[i])) {
				int index = map.get(numbers[i]);
				result[0] = index;
				result[1] = i;
				break;
			} else {
				map.put(target - numbers[i], i);
			}
		}
		return result;
	}

	public static void main(String[] args) {
		int[] input = { 2, 7, 11, 15 };
		int[] output = twoSum(input, 9);
		int count = 1;
		for (int i : output) {
			System.out.println("Index" + (count++) + ": " + i);
		}
	}
}

Time complexity depends on the put and gets operations of HashMap which is normally O(1). The time complexity of this solution is O(n).

Solution:
Here is another solution without using the HashMap. Please write a comment if anything wrong.

package com.algorithm.twosum;

public class TwoSum {

	static int[] input = { 2, 7, 11, 15 };
	static int target = 9;

	public static void main(String[] args) {
		int index = 1;
		for (Integer indexes : twoSumSolution(input, target)) {
			System.out.println("Index" + (index++) + ":" + indexes);
		}
	}

	private static int[] twoSumSolution(int[] input2, int target) {
		int[] output = new int[2];
		int counter = 0;
		boolean flag = false;
		for (int i = 0, j = 1; i < input.length; i++) {
			if (target == (input[i] + input[j])) {
				output[0] = i;
				output[1] = j;
				flag = true;
			}
			counter++;
			if (flag) {
				break;
			}
		}
		System.out.println("Total Loop Count: " + counter);
		return output;
	}
}

Time complexity is O(1) in the best case and O(n) in the worst case.

Two Sum || Input array is sorted
This problem is similar to Two Sum. To solve this problem, we can use two points to scan the array from both sides. See Java solution below:

Solution:

package com.algorithm.twosum;

public class TwoSum2 {

	static int[] input = { 2, 7, 11, 15 };
	static int target = 9;

	public static void main(String[] args) {
		int index = 1;
		for (int indexes : twoSum(input, target)) {
			System.out.println("Index" + (index++) + ":" + indexes);
		}
	}

	public static int[] twoSum(int[] numbers, int target) {
		if (numbers == null || numbers.length == 0)
			return null;
		int i = 0;
		int j = numbers.length - 1;
		while (i < j) {
			int x = numbers[i] + numbers[j];
			if (x < target) {
				++i;
			} else if (x > target) {
				j--;
			} else {
				return new int[] { i, j };
			}
		}
		return null;
	}
}

Two Sum ||| Data Structure Design
Design and implement a TwoSum class. It should support the following operations. add and find

add – add the number to an internal data structure. find – find if there exists any pair of numbers which sum is equal to the value.

For Example:
          add(1);
          add(3);
          add(5);
          find(8);  ==> True
          find(6); ==> False

Solution:
Since the desired class need add and get operations, HashMap is a good option for this.

package com.algorithm.twosum;

import java.util.HashMap;

public class TwoSum3 {

	private static HashMap<Integer, Integer> elements = new HashMap<Integer, Integer>();

	public static void add(int number) {
		if (elements.containsKey(number)) {
			elements.put(number, elements.get(number) + 1);
		} else {
			elements.put(number, 1);
		}
	}

	public static boolean find(int value) {
		for (Integer i : elements.keySet()) {
			int target = value - i;
			if (elements.containsKey(target)) {
				if (i == target && elements.get(target) < 2) {
					continue;
				}
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		add(3);
		add(5);
		add(6);
		System.out.println("Check if value 8 exists or not? " + find(8));
		System.out.println("Check if value 10 exists or not? " + find(10));
	}
}