Sunday, December 28, 2014

Self Excluding Product

/**
 * Implement a method which takes an integer array and returns an integer array (of equal size) in
 * which each element is the product of every number in the input array with the exception of the
 * number at that index.
 *
 * Example:
 *   [3, 1, 4, 2] => [8, 24, 6, 12]
 */
public int[] selfExcludingProduct(int[] input) {
    // implementation...
}
Click here for original problem.


Update 2016-10-05

A neater solution. Go through the array twice. First time get the product of all numbers previous to current number, second time get products after current number.


    public int[] productExceptSelf(int[] nums) {
        int len = nums.length;
        int[] rst = new int[len];
        if (len == 0) {
            return rst;
        }
        rst[0] = 1;
        for (int i = 1; i < len; i++) {
            rst[i] = rst[i - 1] * nums[i - 1];
        }
        int p = nums[len - 1];
        for (int i = len - 2; i >= 0; i--) {
            rst[i] *= p;
            p *= nums[i];
        }
        return rst;
    }


public class SelfExcludingProduct {
 public int[] selfExcludingProduct (int[] input) {
  if (input == null) 
   throw new NullPointerException ("Null input array!");
  int[] productArray = new int[input.length];
  if (input.length == 0) 
   return productArray;
  int product = 1;
  int numOfZeros = 0;
  for (int i = 0; i < input.length; i++) {
   if (input[i] != 0)
    product *= input[i];
   else
    numOfZeros++;
   if (numOfZeros >= 2) {
    return productArray;
   }
  }
  for (int i = 0; i < input.length; i++) {
   if (numOfZeros == 0) {
    productArray[i] = product / input[i];
   }
   else {
    if (input[i] == 0) 
     productArray[i] = product;
    else
     productArray[i] = 0;
   }
    
  }
  
  return productArray;
   
 }

}

No comments:

Post a Comment