## Amazon Interview Question for SDE1s

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
9
of 9 vote

Calculate product of entire array checking for zero's and neglecting them.
On second pass through array if we calculate for each element product/element[i] if element is nonzero and assign for each zero element just product

Comment hidden because of low score. Click to expand.
1
of 1 vote

Not sure if you wanna do that. If it has a zero somewhere then I think the correct behaviour is to have all the other elements (except the zero element) yield zeroes.

Comment hidden because of low score. Click to expand.
0

Also check whether 2 or more zero is present. If so replace the entire array with 0s.

Comment hidden because of low score. Click to expand.
0

public static int[] replaceTerms(int[] a ){

int product = 1;
int zeroes = 0 ;
for (int n : a) {
if(n == 0){

zeroes++;
continue;
}
product*=n;

}

if(zeroes>=2) {
Arrays.fill(a, 0);
return a;
}else if(zeroes == 1){
for (int i = 0 ; i<a.length ;i++) {
if (a[i] == 0) a[i] = product;
else a[i] = 0;
}
}else {
for (int i = 0 ; i<a.length ;i++)
a[i] = product/a[i];
}
return a;

}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

The problem can be solved via brute-force O(N^2) or in optimal O(N). I am proposing the following solution:
(i) compute tow cumulative products 'cpl[]' and 'cpr[]', one form left to right, the latter one form right to left
(ii) for each position 'idx' in the array compute the product of the left and right positions in respective cumulative arrayd, hence a[idx] = cpl[idx-1]*cpr[idx+1]; If index is out of bounds ignore it;

Notice that the left cumulative product need not be computed as you can keep track of the cumulative product 'on fly' as you finally go through the array a[]. In the following code the cpl[] is used for brevity.

A sample code is shown below:

public void exclusiveProduct(int a[]) {
int N = a.length;
int[] cpl = new int[N]; 	% cumulative products
int[] cpr = new int[N];

//  Initialize cumulative products
cpl[0]  	= a[0];
cpr[N-1] 	= a[N-1];

for (int k = 1; k<N ;k++) {
int j = N-1-k;
cpr[j] = cpl[j+1] * a[j];
cpl[k] = cpl[k-1] * a[k];
}

// Replace elements within the input array
for (int k = 0; k<N ;k++) {
int left  	= (k-1)>0?cpl[k-1]:1;
int right 	= (k+1)<N?cpr[k+1]:1;
a[k] = left*right;
}
}

I hope it works.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int arr[] = { 1, 2, 3 };
const int prod = std::accumulate(begin(arr), end(arr), 1, std::multiplies<int>());
std::transform(begin(arr), end(arr), begin(arr), [&prod](int el) {return el != 0 ? prod / el : 0; });

Comment hidden because of low score. Click to expand.
0
of 0 vote

function product( a ) {
if  ( a.length ) return a.pop () * product ( a );
return 1;
};

function f ( arr ) {
var newArr = [];
if ( arr.slice () ) {
for ( var i = 0; i < arr.length; i++ ) {
var temp = Array.concat ( arr.slice ( 0, i ), arr.slice ( i + 1 ) );
newArr.push ( product ( temp ) );
};
};
return newArr;
};

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) but good starting ground before optimizing your code:

void arrayProduct(int arr[]) {
int arrLength = arr.length();
if (arrLength  > 1) {
int product = 1;
for (int j = 0; j < arrLength ; j++) {
if (j != i) {
product *= arr[j];
}
}
arr[i] = product;
product = 1;
}
}

Comment hidden because of low score. Click to expand.
0

My bad, rushed the typing of the code after writing it on paper:

void arrayProduct(int arr[]) {
int arrLength = arr.length();
if (arrLength  > 1) {
for (int i = 0; i < arrLength; i++) {
int product = 1;
for (int j = 0; j < arrLength; j++) {
if (j != i) {
product *= arr[j];
}
}
arr[i] = product;
product = 1;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) but good starting ground before optimizing your code:

void arrayProduct(int arr[]) {
int arrLength = arr.length();
if (arrLength  > 1) {
int product = 1;
for (int j = 0; j < arrLength ; j++) {
if (j != i) {
product *= arr[j];
}
}
arr[i] = product;
product = 1;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done in O(n)

void calculateArray(int []a){

int product=1;

for(int i=0;i<a.length;i++){
product=product*a[i];
}

for(int i=0;i<a.length;i++){

a[i]=product/a[i];
}

Comment hidden because of low score. Click to expand.
0

This solution will not work if array has any element as zero

Comment hidden because of low score. Click to expand.
0

if array has any element as zero, we can put the if condition for that case

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] arrayOfProduct(int[] a) {
int product=1;
int [] arrayProduct = new int[a.length];

for (int i = 0; i < a.length; i++) {
arrayProduct[i] = product;
product*=a[i];
}
product=1;
for (int i = a.length-1; i >= 0; i--) {
arrayProduct [i] *= product;
product*= a[i];
}

return arrayProduct ;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the product of the array. Replace each element by product/element

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done using an auxillary array. For each element in array A, store product of previous elements in auxillary array store[] in first pass from left to right. And in second pass, keep product of elements from right to left.

Example A[]={5,7,8,2}, Store[]={1,1,1,1}
Now move from left to right and fill Store[] like this,
Store[]={1,5,35,280}
Store[i] gives the value of product of elements on left side of A[i], excluding A[i].
Now move from right to left, keep product of right elements in a variable and replace the product accordingly.
Take a look at my implementation for clear understanding :)

void replaceElem(int arr[],int n)
{
int *store = new int[n];
memset(store,1,sizeof(store)); // Initialize each cell with 1
int temp=1;
for(int i=0;i<n;i++) // this stores product of left elements excluding the element
{
store[i]=temp;
temp=temp*arr[i];
}
temp=1;
for(int i=n-1;i>=0;i--) // this
{
store[i]=temp*store[i];
temp=temp*arr[i];
arr[i]=store[i]; 		// it replace the appropriate value
}
free(store);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.List;
public class ReplaceMatrixByProducts
{

public static void main(String[] args)
{
int[] a={2,3,1,4};
int product=1;
int zeroCount=0;

//Get product of all elements
for (int i = 0; i < a.length; i++)
{
if(a[i]==0) zeroCount++;
product*=product;
}

for (int i = 0; i < a.length; i++)
{
/*
* if there are more than 2 zeros in array then all the prodcuts will be zero
*/
if(zeroCount>1)
{
a[i]=0;
}
else if(zeroCount==1) //there is only one zero
{
if(a[i]==0)
a[i]=product;
else
a[i]=0;
}
else //there are no zeros
{
a[i]=product/a[i];
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Ex {
public static void multiplyRest(int[] a) {
int product = 1;
int zIdx = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
product *= a[i];
} else {
if (zIdx != -1) {
fillWithZeros(a);
return;
}
zIdx = i;
}
}

if (zIdx != -1) {
fillWithZeros(a);
a[zIdx] = product;
return;
}

for (int i = 0; i < a.length; i++) {
a[i] = product / a[i];
}
}

private static void fillWithZeros(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = 0;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

class Ex {
public static void multiplyRest(int[] a) {
int product = 1;
int zIdx = -1;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0) {
product *= a[i];
} else {
if (zIdx != -1) {
fillWithZeros(a);
return;
}
zIdx = i;
}
}

if (zIdx != -1) {
fillWithZeros(a);
a[zIdx] = product;
return;
}

for (int i = 0; i < a.length; i++) {
a[i] = product / a[i];
}
}

private static void fillWithZeros(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = 0;
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

First, pass through the array and check how many 0s there are. If there is more than one zero, then all the array elements in the output array MUST be 0.

If there is only one 0, then replace it with a 1.

After our first pass through, we will go through the array and get the product of all the array elements. let's call this product x.

Finally, we go through the array and for each element "e" in the array, its corresponding value in the new array will be x/e.

This algorithm would, thus, run in O(3n) = O(n).

I'm pretty sure that it would also work with negative numbers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
* You are given an array,
* you have to replace each element of the array with product of the rest element.
* Example: {1,2,3}==> {6,3,2}
*/
def rest(xs:List[Int]):List[Int] = {
val product = xs.reduce(_*_)
xs.map(x => if(x==0) product else product/x)
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Integer[] arryInt = {2,3,5};

Integer[] clone = arryInt.clone();

for(int i=0 ; i<arryInt.length; i++) {

int product = 1;
for(int j=arryInt.length-1;j>=0;j--)
{
if(j != i)
product = product * arryInt[j];
}

clone[i] = product;

}

System.out.println(Arrays.toString(clone));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Integer[] arryInt = {2,3,5};

Integer[] clone = arryInt.clone();

for(int i=0 ; i<arryInt.length; i++) {

int product = 1;
for(int j=arryInt.length-1;j>=0;j--)
{
if(j != i)
product = product * arryInt[j];
}

clone[i] = product;

}

System.out.println(Arrays.toString(clone));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Code {

public static void main(String[] args) {

Integer[] arryInt = {2,3,5};

Integer[] clone = arryInt.clone();

for(int i=0 ; i<arryInt.length; i++) {

int product = 1;
for(int j=arryInt.length-1;j>=0;j--)
{
if(j != i)
product = product * arryInt[j];
}

clone[i] = product;

}

System.out.println(Arrays.toString(clone));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Code {

public static void main(String[] args) {

Integer[] arryInt = {2,3,5};

Integer[] clone = arryInt.clone();

for(int i=0 ; i<arryInt.length; i++) {

int product = 1;
for(int j=arryInt.length-1;j>=0;j--)
{
if(j != i)
product = product * arryInt[j];
}

clone[i] = product;

}

System.out.println(Arrays.toString(clone));
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Integer[] arryInt = { 2, 3, 5 };

Integer[] clone = arryInt.clone();

for (int i = 0; i < arryInt.length; i++) {

int product = 1;
for (int j = arryInt.length - 1; j >= 0; j--) {
if (j != i)
product = product * arryInt[j];
}

clone[i] = product;

}

System.out.println(Arrays.toString(clone));

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String[] args) {

Integer[] arryInt = { 2, 3, 5 };

Integer[] clone = arryInt.clone();

for (int i = 0; i < arryInt.length; i++) {

int product = 1;
for (int j = arryInt.length - 1; j >= 0; j--) {
if (j != i)
product = product * arryInt[j];
}

clone[i] = product;

}

System.out.println(Arrays.toString(clone));
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

function replaceArray(int[] arrArg) {
arrProd=1;
zerosCount=0;
oneZeroIndex=arrArg.length;

for(int i=0;i<arrArg.length;i++) {
if (arrArg[i]==0) {
zerosCount+=1;
oneZeroIndex=i;
} else {
arrProd *= arrArg[i]
}
if (zerosCount>1) {
//if more than one zero found then return array with zeros
for(int i=0;i<arrArg.length;i++) {
arrArg[i]=0;
return;
}
}
}

//I am just doing some fancy stuff here to eliminate the need of checking the Zero in each loop since I already
//have it's index in the first loop
//more complex, but more efficient.
for(int i=0; i<oneZeroIndex; i++) {
arrArg[i] = arrProd / arrArg[i];
}

//if no zeros found then completed
if (oneZeroIndex == arrArg.length) {
return;
}

arrArg[oneZeroIndex] = arrProd;

//This loop will only run if we have a zero.
for(int i=oneZeroIndex+1;i<arrArg.length;i++)
{
arrArg[i] = arrProd/arrArg[i];
}

return;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

function replaceArray(int[] arrArg) {
arrProd=1;
zerosCount=0;
oneZeroIndex=arrArg.length;

for(int i=0;i<arrArg.length;i++) {
if (arrArg[i]==0) {
zerosCount+=1;
oneZeroIndex=i;
} else {
arrProd *= arrArg[i]
}
if (zerosCount>1) {
//if more than one zero found then return array with zeros
for(int i=0;i<arrArg.length;i++) {
arrArg[i]=0;
return;
}
}
}

//I am just doing some fancy stuff here to eliminate the need of checking the Zero in each loop since I already
//have it's index in the first loop
//more complex, but more efficient.
for(int i=0; i<oneZeroIndex; i++) {
arrArg[i] = arrProd / arrArg[i];
}

//if no zeros found then completed
if (oneZeroIndex == arrArg.length) {
return;
}

arrArg[oneZeroIndex] = arrProd;

//This loop will only run if we have a zero.
for(int i=oneZeroIndex+1;i<arrArg.length;i++)
{
arrArg[i] = arrProd/arrArg[i];
}

return;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int i = 1;
for(i=0; i<a.length; i++)
{
j=j*a[ i ];
}

for(i=0; i<a.length; i++)
{
a[ i ] = j / a[ i ];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1- simply get the product of all elements of array in O(n)
2- for every element in array value will be total multiply / arr[i] in O(n)
total is O(2n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>

int main ()
{
int array_in[] = {1,2,3,4,5};
long long product = 1;
int i;
int array_len = sizeof array_in / sizeof *array_in;
int array_out[array_len];
for (i =0; i < array_len ; i++) {
product = product*array_in[i] ;
}
for (i =0; i < array_len ; i++) {
array_out[i] = product/array_in[i];
printf("RESULT - %d\n", array_out[i]);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>

int main ()
{
int array_in[] = {1,2,3,4,5};
long long product = 1;
int i;
int array_len = sizeof array_in / sizeof *array_in;
int array_out[array_len];
for (i =0; i < array_len ; i++) {
product = product*array_in[i] ;
}
for (i =0; i < array_len ; i++) {
array_out[i] = product/array_in[i];
printf("RESULT - %d\n", array_out[i]);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

def subSample(self,A):
output = []
product=1
for j in range(len(A)):
product = product*A[j]
for i in range(len(A)):
output.append(product/A[i])
return output

Comment hidden because of low score. Click to expand.
0
of 0 vote

One could divide the list into two for every element and find the product of each.

def findPdtLists(a,b):
print(a,b,sep='\t')
x=findPdtList(a)
y=findPdtList(b)
return x*y

def findPdtList(a):
pdt=1
for i in a:
pdt=pdt*i
return pdt

def replaceWidPdt(a):
t=[None]*len(a)
for i in range(len(a)):
x=findPdtLists(a[:i],a[i+1:])
t[i]=x
return t

if __name__=='__main__':
a=[1,2,3]
b=replaceWidPdt(a)
print(b)

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public int[] product(int[] arr){
int[] returnArray = new int[arr.length];
int zeroElementIndex = -1;
int product = 1;

for(int i=0;i<arr.length;i++){
if(arr[i] == 0){
zeroElementIndex = i;
break;
}else{
product = product * arr[i];
}
}

if(zeroElementIndex != -1){
product =1;
for(int j=0;j<arr.length;j++){
if(j != zeroElementIndex)
{
returnArray[j] = 0;
product = product * arr[j];
}
}
returnArray[zeroElementIndex] = product;
}else{
for(int j=0;j<arr.length;j++){
returnArray[j] = product/arr[j];
}
}

return returnArray;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

void productArray(int arr[], int n)
{
int i, temp = 1;

/* Allocate memory for the product array */
int *prod = (int *)malloc(sizeof(int)*n);

/* Initialize the product array as 1 */
memset(prod, 1, n);

/* In this loop, temp variable contains product of
elements on left side excluding arr[i] */
for(i=0; i<n; i++)
{
prod[i] = temp;
temp *= arr[i];
}

/* Initialize temp to 1 for product on right side */
temp = 1;

/* In this loop, temp variable contains product of
elements on right side excluding arr[i] */
for(i= n-1; i>=0; i--)
{
prod[i] *= temp;
temp *= arr[i];
}

/* print the constructed prod array */
for (i=0; i<n; i++)
printf("%d ", prod[i]);

return;
}
Time Complexity: O(n)
Space Complexity: O(n)
Auxiliary Space: O(1)

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Javascript with underscore:

_.map([1,2,3], function(num, idx, list){ return _.chain(list).without(num).reduce(function(memo, num){return memo*num}).value() });

Comment hidden because of low score. Click to expand.
0
of 0 vote

_.map([1,2,3], function(num, idx, list){ return _.chain(list).without(num).reduce(function(memo, num){return memo*num}).value() });

Comment hidden because of low score. Click to expand.
0
of 0 vote

In JavaScript with underscore:

_.map([1,2,3], function(num, idx, list){ return _.chain(list).without(num).reduce(function(memo, num){return memo*num}).value() });

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] replaceTerms(int[] a ){

int product = 1;
int zeroes = 0 ;
for (int n : a) {
if(n == 0){

zeroes++;
continue;
}
product*=n;

}

if(zeroes>=2) {
Arrays.fill(a, 0);
return a;
}else if(zeroes == 1){
for (int i = 0 ; i<a.length ;i++) {
if (a[i] == 0) a[i] = product;
else a[i] = 0;
}
}else {
for (int i = 0 ; i<a.length ;i++)
a[i] = product/a[i];
}
return a;

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

If space is not an issue, then another idea besides the

product / array[i]

method is

Let N be the length of the array.

1. Create two temporary arrays,
prodLeft[ N ] & prodRight[ N ],
where, prodLeft[i] contains the product of all elements to the left of array[i], and prodRight[i] contains the product of all elements to the right of array[i]

2. for each element, replace
array[i] = prodLeft[i] * prodRight[i]

So the implementation of this code would look like

public void ReplaceWithProducts(int[] array)
{
if (array.length == 1)
return;

int count = CountZeroes(array);

if (count > 1)
{
// If there are more than 1 0's,
// all the elements will be ultimately 0
replaceWithZeros(array);
return;
}

if (count == 1)
{
// If there's only 1 zero, only the zero
// element will have a non-zero value.
// All other elements will be 0.
long product = 1;
int index = 0;

for (int i = 0; i < array.length; i++)
{
if(array[i] == 0)
{
index = i;
continue;
}

// Compute the product so far.
product = product * array[i];

// Keep setting the element to zero since
// we already have the element's contribution
// in the product.
array[i] = 0;
}
array[index] = product;
return;
}

// If there are no 0's.
int[] prodLeft = new int[array.length];
int[] prodRight = new int[array.length];

prodLeft[0] = 1; // Since there're no elements to the left

prodRight[array.length - 1] = 1; //Since there're no elements to the right of the last one.

for (int i = 1; i < array.length; i++)
{
prodLeft[i] = array[i-1] * prodLeft[i-1];
}

for (int i = array.length -2; i >= 0; i--)
{
prodRight[i] = array[i+1] * prodRight[i+1;]
}

for (int i = 0; i < array.length; i++)
{
array[i] = prodLeft[i] * prodRight[i];
}

}

public int CountZeroes(int[] array)
{
int count = 0;

for (int i = 0; i < array.length; i++)
{
if(array[i] == 0)
{
count++;
}
}
return count;
}

public void replaceWithZeros(int[] array)
{
for (int i=-; i<array.length; i++)
{
array[i] = 0;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArrayProduct {

static int arr[] = {1,2,3};
static int prod[]=new int[arr.length];

public static void main(String[] args) {
product(arr);
}

public static void product(int[] a)
{
int array_size=arr.length;
int temp=1;
boolean zero_element=false;

for(int i=0;i<array_size;i++)
{
prod[i]=temp;
temp=temp*a[i];

if(a[i]==0)
break;
}

temp=1;

for(int i=array_size-1;i>=0;i--)
{
prod[i]=prod[i]*temp;
temp=temp*a[i];
}

for(int i=0;i<array_size;i++)
{
System.out.print(prod[i] + " ");
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArrayProduct {

static int arr[] = {1,2,3};
static int prod[]=new int[arr.length];

public static void main(String[] args) {
product(arr);
}

public static void product(int[] a)
{
int array_size=arr.length;
int temp=1;
boolean zero_element=false;

for(int i=0;i<array_size;i++)
{
prod[i]=temp;
temp=temp*a[i];

if(a[i]==0)
break;
}

temp=1;

for(int i=array_size-1;i>=0;i--)
{
prod[i]=prod[i]*temp;
temp=temp*a[i];
}

for(int i=0;i<array_size;i++)
{
System.out.print(prod[i] + " ");
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

if one element is zero, find the product p of all elements except zero. Set zero as p, rest as zero.
arr=[1,3,0,2]
p=6
arr=[0,0,6,0]

if more than one element is zero, replace every element with zero
arr=[1,0,2,0,3]
arr=[0,0,0,0,0]

else
find product p of all elements
replace every element with p/element
arr=[1,3,4,2]
p=24
arr=[24,8,6,12]

Comment hidden because of low score. Click to expand.
-1
of 1 vote

Step 1: Calculate product of the entire array
Step 2: ans[i]=product/element[i]

Here element refers to the current element at a particular index. ans is the new element that will replace it.

Complexity: O(n)+O(n)=O(n)

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

We can check for 0/0 condition and in rest of the cases it will work fine.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

public static void ArrayProduct(int arr[])
{
int product = 1;

System.out.println(Arrays.toString(arr));

for(int i = 0; i < arr.length; i++)
product *= arr[i];

for (int i = 0; i < arr.length; i++)
arr[i] = product / arr[i];

System.out.println(Arrays.toString(arr));
}

Input: [2, 3, 4, 5, 6]
Output: [360, 240, 180, 144, 120]

Let me know if i am wrong.

Comment hidden because of low score. Click to expand.
0

K, how you handle this test case 1,2,3,0

Comment hidden because of low score. Click to expand.
0

for(int i = 0; i < arr.length; i++)
{
if(arr[i] == 0)
continue;
product *= arr[i];
}

for (int i = 0; i < arr.length; i++)
{
if(arr[i] == 0)
continue;
arr[i] = product / arr[i];
}

I guess this will do.

Comment hidden because of low score. Click to expand.
0

This does not work correctly. If arr[i] is 0, it should be the product of all the other elements when you are done, you code leaves it to be 0. Also, all other elements should be 0 in that case, not product / arr[i], since product is missing the multiplication by 0.

The case with zero is easy to generalize. Scan for zeroes as you calculate product. If you fine only one zero, the element with its index is the product of all other elements. If you find more than one zero, all element will be zero at the end, no need to calculate further. If none of them are zero, you can do the product/a[i] thing at the end.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.