A9 Interview Question
Software Engineer / Developersprod[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;
}
<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));
}
}
//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;
}
1. Multiply all numbers.
- Vaibhav April 12, 20112. 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;