CareerCup

Loop through the array once to find the product of all numbers.
For the output, loop through the array and divide the product / index to find the corresponding value in the index.

private static int[] multiplyData(int[] data) {
		int[] newArray=new int[data.length];
		for(int i=0;i<newArray.length;i++)
		{
			int temp=1;
			for(int j=0;j<newArray.length;j++)
			{
				if(i!=j)
				{
					temp*=data[j];
				}
			}
			newArray[i]=temp;
			
		}
		return newArray;
	}

# Assume this is inside a method/function/proc/subroutine/whatever...
# Assume input array is IN and output is OUT
# {In java, we can declare new arrays off heap are zero initialized... assume that or zero initialize it on creation somehow... }

int zeroIndex = -1;
double prod = 1;

# Find zeros in input while accumulating product of
# all non-zero elements
for( int i=0; i < IN.length ; i++ )
{	
	# Found zero element
	if( IN[i] == 0 )
	{
		# This is second one found, so return OUT as is
		if ( zeroIndex >= 0 ) { return OUT; }

		# Save spot of zero
		zeroIndex = i;
		continue;
	}
	prod *= IN[i];
}

# Case where there was 1 zero...
if ( zeroIndex >= 0) 
{
	OUT[zeroIndex] = prod;
	return OUT;
}

# Calculate output array (in this case, all elements of IN were nonzero)
for( int i=0; i < IN.length ; i++ )
{	
	OUT[i] = prod / IN[i];
}
return OUT;

Ping me for job opportunities in Toronto/Waterloo area.

n: no. of element in input array.
following function can have 2n complexity.

function multiArr(iptArr){
	var i=0; //counter
	var prdt=1; //product of elements in input array
	for(i=0;i<iptArr.length;i++){ //find product
		if(iptArr[i]!==0)	 //if not zero
			prdt*=iptArr[i]; 
	}
	var newArr=[]; //array to be returned
	for(i=0;i<iptArr.length;iptArr++){
		newArr[i]=prdt/iptArr[i];	//except index
	}
	return (newArr);
}

void mulExceptIndex(int iArr[])
{
	int resultArr[SIZE];
	int product=1;

	for(int i=0;i<SIZE;i++)
		product = product * iArr[i];
	
	for(int i=0;i<SIZE;i++)
	{
		if(iArr[i]!=0)
		resultArr[i] = product/iArr[i];
	}
}

///
package Algo;

public class ArrayMultiplication {
//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value

public static void main(String args[]) {

int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;

int product = 1;
int i = 0;
int zerocounter = 0;

// Does input array have zero value?
while (i < A.length) {
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all non-zero inputs
}
i++;
}

if (zerocounter <= 1) { // Does the input array have less than two zeroes?

B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

for (int k = 0; k < B.length; k++) {
System.out.println("Array" + B[k]);
}
}

}
\\\

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
		int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
		int B[] = null; 
		int product = 1;  
		int i = 0;
		int zerocounter = 0;

		while (i < A.length) { 		// Does input array have zero value? 
			if (A[i] == 0) {
				zerocounter += 1; // if yes, how many zeroes?
			} else {
				product = product * A[i]; // multiply all non-zero inputs
			}
			i++;
		}
		if (zerocounter <= 1) { // Does the input array have less than two zeroes?
			B = new int[A.length]; // output array initialization
			i = 0;
			while (i < A.length) { 
				if (A[i] == 0) {
					B[i] = product; // product of all non-zeroes
				}else{
					B[i] = product/A[i]; // product / ith input = product of all non-ith elements
				}
				i++;
			}
		}

//Assumption : the input array is not empty
		//Assumption : the multiplication product does not exceed the integer max value
		int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
		int B[] = null; 
		int product = 1;  
		int i = 0;
		int zerocounter = 0;

		while (i < A.length) { 		// Does input array have zero value? 
			if (A[i] == 0) {
				zerocounter += 1; // if yes, how many zeroes?
			} else {
				product = product * A[i]; // multiply all non-zero inputs
			}
			i++;
		}
		if (zerocounter <= 1) { // Does the input array have less than two zeroes?
			B = new int[A.length]; // output array initialization
			i = 0;
			while (i < A.length) { 
				if (A[i] == 0) {
					B[i] = product; // product of all non-zeroes
				}else{
					B[i] = product/A[i]; // product / ith input = product of all non-ith elements
				}
				i++;
			}
		}

//Assumption : the input array is not empty
		//Assumption : the multiplication product does not exceed the integer max value
		int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
		int B[] = null; 
		int product = 1;  
		int i = 0;
		int zerocounter = 0;

		while (i < A.length) { 		// Does input array have zero value? 
			if (A[i] == 0) {
				zerocounter += 1; // if yes, how many zeroes?
			} else {
				product = product * A[i]; // multiply all non-zero inputs
			}
			i++;
		}
		if (zerocounter <= 1) { // Does the input array have less than two zeroes?
			B = new int[A.length]; // output array initialization
			i = 0;
			while (i < A.length) { 
				if (A[i] == 0) {
					B[i] = product; // product of all non-zeroes
				}else{
					B[i] = product/A[i]; // product / ith input = product of all non-ith elements
				}
				i++;
			}
		}

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;
int product = 1;
int i = 0;
int zerocounter = 0;

while (i < A.length) { // Does input array have zero value?
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all other inputs
}
i++;
}
if (zerocounter <= 1) { // Does the input array have less than two zeroes?
B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;
int product = 1;
int i = 0;
int zerocounter = 0;

while (i < A.length) { // Does input array have zero value?
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all other inputs
}
i++;
}
if (zerocounter <= 1) { // Does the input array have less than two zeroes?
B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

//Assumption : the input array is not empty
//Assumption : the multiplication product does not exceed the integer max value
int[] A = { 2, 2, 3, 4, 5, 6, -1, -1 }; //input array
int B[] = null;
int product = 1;
int i = 0;
int zerocounter = 0;

while (i < A.length) { // Does input array have zero value?
if (A[i] == 0) {
zerocounter += 1; // if yes, how many zeroes?
} else {
product = product * A[i]; // multiply all other inputs
}
i++;
}
if (zerocounter <= 1) { // Does the input array have less than two zeroes?
B = new int[A.length]; // output array initialization
i = 0;
while (i < A.length) {
if (A[i] == 0) {
B[i] = product; // product of all non-zeroes
}else{
B[i] = product/A[i]; // product / ith input = product of all non-ith elements
}
i++;
}
}

public static void main(String[] args) {
        int[] array = {1, 2, 3, 4};
        int size = array.length;
        int[] result = new int[size];
        int temp = 1;
        for(int i = 0; i < size ; i++){
            temp = 1;
            for(int j = size-1 ; j >=0; j--){
                temp = temp * array[j];
            }
            result[i] = temp / array[i];
        }

        for(int value : result){
            System.out.println(value);
        }

}

public static void main(String[] args) {
        int[] array = {1, 2, 3, 4};
        int size = array.length;
        int[] result = new int[size];
        int temp = 1;
        for(int i = 0; i < size ; i++){
            temp = 1;
            for(int j = size-1 ; j >=0; j--){
                temp = temp * array[j];
            }
            result[i] = temp / array[i];
        }

        for(int value : result){
            System.out.println(value);
        }
    }

public void printMultiply(int[] arr){
	int nozero = 0;
	double prod = 1;
	for(int i=0;i<arr.length;i++){
		if(arr[i]!=0){
			prod*=arr[i];
		}else{
			nozero++;
		}
		if(nozero>1){
			break;
		}
	}
	if(nozero>1){
		for(int i=0;i<arr.length;i++){
			System.out.print("0");
		}
	}else{
		for(int i=0;i<arr.length;i++){
			if(nozero>0&&arr[i]!=0){
				System.out.print("0");
			}else{
				if(arr[i]==0){
					System.out.print(prod);
				}else{
					System.out.print(prod/arr[i]);
				}
			}
		}
	}
}

int[] multiplyData(int[] data) {
		int[] newArray = new int[data.length];

		int zerothIndex = -1;
		int zero = 0;
		int pdt = 1;
		for (int i = 0; i < newArray.length; i++) {
			if (data[i] == 0) {
				zero++;
				zerothIndex = i;
			} else {
				pdt = pdt * data[i];
			}
		}
		if (zero >= 2) {
			return newArray; // everything will be 0
		}
		if (zero == 1) {
			newArray[zerothIndex] = pdt;
			return newArray;
		}
		for (int i = 0; i < newArray.length; i++) {
			newArray[i] = pdt / data[i];
		}

		return newArray;
	}

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

int[] multiplyData(int[] data) {
int[] newArray = new int[data.length];

int zerothIndex = -1;
int zero = 0;
int pdt = 1;
for (int i = 0; i < newArray.length; i++) {
if (data[i] == 0) {
zero++;
zerothIndex = i;
} else {
pdt = pdt * data[i];
}
}
if (zero >= 2) {
return newArray; // everything will be 0
}
if (zero == 1) {
newArray[zerothIndex] = pdt;
return newArray;
}
for (int i = 0; i < newArray.length; i++) {
newArray[i] = pdt / data[i];
}

return newArray;
}

def find_prod(a):
	n = len(a)
	zero_idx = -1
	zero_count = 0
	prod = 1
	for i in range(n):
		if a[i] is 0:
			if not zero_count:
				zero_idx = i
				zero_count += 1
			else:
				zero_count += 1
				prod = 0
		else:
			prod *= a[i]
			
	if zero_count > 1:
		return [0]*n
	elif zero_count is 1:
		return [prod if i is zero_idx else 0 for i in range(n)]
	else:
		return [prod/a[i] for i in range(n)]

1) Get the combinations of input array's indices, for example: (0, 1), (1, 2), (1, 2, 3), (0, 1, 2, 3, 4)....

2) Then multiply the elements pointed by the indices combination.

3) remove duplicates, ...

public class MultiplyAllNumbers {

	public static void main(String[] args) {

		int[] ip = { 1, 2, 3, 4 };
		Set<Integer> origins = new HashSet<Integer>();
		for(int i=0; i<ip.length; i++){
			origins.add(ip[i]);
		}
		
		Set<Integer> op = new HashSet<Integer>();

		int length = ip.length;
		
		for(int i=2; i<=length; i++){
			
			Set<Set<Integer>> set = getCombinationOfMNumbersFromN(i, length);
			Iterator<Set<Integer>> itr = set.iterator();
			while(itr.hasNext()){
				int product = 1;
				
				Set<Integer> subSet = itr.next();
				Iterator<Integer> subItr = subSet.iterator();
				while(subItr.hasNext()){
					product = product*ip[subItr.next()];
				}
				
				if(!origins.contains(product)){
					op.add(product);
				}
			}
			
		}

		System.out.println(op);
	}

	// get m different numbers from (0, 1, ..., (n-1)).
	public static Set<Set<Integer>> getCombinationOfMNumbersFromN(int m, int n) { 

		Set<Set<Integer>> resultSet = new HashSet<Set<Integer>>();
		getCombinationOfMNumbersFromN(m, n, 1, -1, resultSet, null);
		return resultSet;
	}

	/**
	 * 
	 * @param m
	 * @param n
	 * @param index
	 *            is the index of element in current set, from 1 to m.
	 * @param preNumber
	 *            is the previous number added to current set.
	 * @param resultSet
	 * @param currentSet
	 */
	private static void getCombinationOfMNumbersFromN(int m, int n, int index,
			int preNumber, Set<Set<Integer>> resultSet, Set<Integer> currentSet) {

		if (index == (m + 1)) {

			Set<Integer> set = new HashSet<Integer>(); // Java pass object by
														// reference, so need
														// create a new object
														// to store the data.
			set.addAll(currentSet);
			resultSet.add(set);

			return;
		}

		for (int i = preNumber + 1; i < (n - m + index); i++) {
			if (index == 1)
				currentSet = new HashSet<Integer>();
			currentSet.add(i);
			getCombinationOfMNumbersFromN(m, n, index + 1, i, resultSet,
					currentSet);
			currentSet.remove(i);
		}

	}

}

// No of multiplication (n-1) where n is the size of matrix and time complexity is O(n) and space complexity is O(1)
        void function(int[] arr) {
                
                int multiply = 1;
                for(int index=0; index<arr.length; index++) {
                        multiply*=arr[index];
                }
                
                for(int index=0; index < arr.length; index++) {
                        System.out.print(multiply/arr[index] + " ");
                }
        }

public static int[] multiplyExceptIndex(int[] arr)
        {
            int product = 1;
            List<int> resultArray = new List<int>();
            
            foreach(int i in arr)
            {
                if(i!=0)
                {
                    product = product * i;
                }
            }

            for(int i=0;i<arr.Length;i++)
            {
                if(arr[i]!=0)
                {
                    resultArray.Add(product / arr[i]);
                }
                else
                {
                    resultArray.Add(0);
                }
            }
           return resultArray.ToArray();
        }

Complexity is O(n + n) = O(n)

public static int[] solution(int[] a) {
		if(a == null || a.length == 0) return a;
		
		int[] res = new int[a.length];
		int mul = a[0];
		for(int i = 1; i < a.length; i++) {
			if(a[i] != 0)
				mul = mul * a[i];
		}
		
		for(int i = 0; i < res.length; i++) {
			if(a[i] != 0)
				res[i] = mul/a[i];
		}
		
		return res;