CareerCup

1. Multiply all numbers.
2. Divide the product by each number in array.

Eg.

arr[] = {2, 3, 4, 5};
prod_all = 2 * 3 * 4 * 5;
prod_1 = prod_all / 2;
prod_2 = prod_all / 3;
prod_3 = prod_all / 4;
prod_4 = prod_all / 5;

prod[i] = (a[0]*a[1]*...*a[i-1]) * (a[i+1]*...*a[n-1]) = prefix[i] * postfix[i]
time complexity: O(n);

int *ProdArray(int *a, int n)
{
	int *prefix, *postfix;
	int i;

	prefix = (int*)malloc(sizeof(int)*n);
	postfix = (int*)malloc(sizeof(int)*n);
	prefix[0] = 1, postfix[n-1] = 1;
	for(i=1; i<n; i++){
		prefix[i] = prefix[i-1]*a[i-1];
		postfix[n-i-1] = postfix[n-i]*a[n-i];
	}
	for(i=0; i<n; i++)
		prefix[i] = prefix[i]*postfix[i];
	free(postfix);
	return prefix;
}

plz explain the question with eg. R u saying product of all element except ith element?

steven.shi's methods should work, but Vaibhav's would fail if there's 0's in the array.

You have to check for 0 in the array and take care of that as well!

I know it is not mentioned in the question, but is it solvable in O(1) space? What if that comes up as a follow up question?

flag=0;
prod=1;
for(i=0;i<n;i++)
{
if(arr[i]==0)
{flag=1; break; }
prod*=arr[i];
}
if(flag)
{
arr[i]=prod;
for(j=0;j<i;j++)
arr[i]=0;
for(j=i+1;j<n;j++)
{arr[i]*=arr[j];
arr[j]=0;}
}
else
{
for(i=0;i<n;i++)
arr[i]=prod/arr[i];
}

<pre lang="" line="1" title="CodeMonkey25723" class="run-this">/* I think this should cover the edge cases */

def prod( myList ):
prod = 1
numZeros = 0
for a in myList:
if a != 0:
prod *= a
else:
numZeros += 1
return prod, numZeros

def prodN1( myList ):
if not len( myList ):
print 0
total, zeros = prod( myList )
for i,a in enumerate( myList ):
if a == 0:
if zeros == 1:
print 'Product without element', i, total
else:
print 'Product without element', i, 0
else:
if zeros == 0:
print 'Product without element', i, total/a
else:
print 'Product without element', i, 0 </pre><pre title="CodeMonkey25723" input="yes">
</pre>

public class App {
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 0};
		double product = 1;
		double counter = 0;
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] != 0) {
				product = product * arr[i];
				counter++;
			}
		}
		System.out.println("Answer: " + Math.pow(product, --counter));
	}
}

for(int k=0;k<=n;k++)
{for(int i=0;i<n;i++)
t=c[k];
c[k]=1;
product=product*c[i];

}
c[k]=t;
}

public double getProductOfGroups(int[] inputArray)
	{
		if(inputArray == null)
			return Integer.MIN_VALUE;
		
		int n= inputArray.length;
		
		if(n==0)
			return Integer.MIN_VALUE; 
		
		double res = 1;
		
		for(int eachNumber : inputArray)
			res*= eachNumber; 
		
		return Math.pow(res, n-1);
		
	}

//Time: O(n),	space: O(1)
	public int [] getProductOfGroups(int[] Array)
		{
			if(Array == null||Array.length<=1)
				return null;
			int [] ret=new int [Array.length];
            boolean isZero=false;
            int zeroIndex=-1;
            int total=1;
            for(int i=0;i<Array.length;++i)
				if(Array[i]==0){
					isZero=true;
					zeroIndex=i;	
				}
	        for(int i=0;i<Array.length;++i){
				if(i!=zeroIndex)
					total*=Array[i];	
			}
	                if(isZero){
				ret[zeroIndex]=total;
			}
			else{
				for(int i=0;i<Array.length;++i)
					ret[i]=total/Array[i];
			}

			return ret;                
			
		}