CareerCup

You can do it in 2N traversals. That is O(n). First find the product of N numbers and store it in a variable. Then, in the second traversal, traverse the array and divide by the element in each index and print the value.

I think question will be more interesting if we do the same without using division operator.
Ok, this also can be done in 2N element traversal. Just giving the possibility of questions to be asked!!

Assumption: All integers are unique (I explained for non-unique case below with some more assumptions)

If a zero exists:
product of non-zero values - just one value as output.
If no zeros:
take the product of all values in one iteration.
do second iteration - for each current value, o/p = product/current_value;
this will give n values of output.

If values are NOT unique:

if one zero: output=product of rest
if more than one zero: output=0 (just one output)
if no zeros: same as non-unique case (note that there will be repetition of values - assuming no deduping required.)

the code in java

package practicepackage;

public class SpecialMultiplication{

public static void main(String[] args)
{
	int[] numbers={1,2,3,4};
	int value=1;
	for(int i=0;i<numbers.length;i++)
	{
		value*=numbers[i];
	}
	for(int j=0;j<numbers.length;j++)
	{
		numbers[j]= value/numbers[j];
	}
	for(int k=0;k<numbers.length;k++)
	{
		System.out.println(numbers[k]);
	}
}

}

#include<stdio.h>

int main(){
int array[] = { 4 , 0 , 7 , 6 , 8 , 0 , 8 , 78, 79, 2};
int len = 10;
long int product;
int i = 0;
int count = 0;

for(i = 0 ; i < len ; i++){
    if(array[i]==0){
        count++;
        continue;
    }
    product *= array[i];
}

for(i = 0 ; i < len ; i++){
    if(array[i])
        printf("%ld\t", (product/array[i]) );
    else{
        if(count = 1)    // IF THERE IS ONE 0 IN THE ARRAY
           printf("%ld", product );
        if(count > 1)    // HANDLES MULTIPLE 0s CASE
            printf("%d" , 0);
    }
}
}

def multiply(alist):
	flist = [1] * len(alist)
	blist = [1] * len(alist)
	for i in range(1, len(alist)):
		flist[i] = alist[i - 1] * flist[i - 1]
	for i in range(len(alist) - 2, -1, -1):
		blist[i] = alist[i + 1] * blist[i + 1]
		
	return [x * y for x, y in zip(flist, blist)]

this is like calculating the product of all numbers in array except current element

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)

#include<iostream>
using namespace std;
#define N 8

int main(){
int A[]= {2, 3, 5, 40, 10, 16, 100, 9};
int i;
long long int pro=1;

for(i= 0; i< N; i++){
pro*= A[i];
}
for(i= 0; i<= N; i++)
cout<<pro/A[i]<<" ";
return 0;
}

Let m=Multiplication of all numbers
output(i) =m/i;

Construct two auxiliary arrays as follows :
A[0] = input[0]
A[i] = A[i-1]*input[i]
B[n-1] = input[n-1]
b[i] = b[i+1]*input[i]
Then, output[i]=a[i-1]*b[i+1]

public class GenerateProduct{
public static void generateProduct(int[] input){
long product = 1;
int count = 0;
int len = input.length;

for(int i : input){
if(i == 0){
count++;

if(count == 2){
for(int j = 0; j< len; ++j){
System.out.println(0);
}
return;
}

continue;
}
product *= i;
}


for(int i : input)
{
if(count == 1){
if(i == 0){
System.out.println(product);
continue;
}
else{
System.out.println(0);
continue;
}
}
else
System.out.println(product/i);
}

}
}

public class GenerateProduct{
    public static void generateProduct(int[] input){
    	long product = 1;
    	int count = 0;
    	int len = input.length;
	
    	for(int i : input){
    		if(i == 0){
    			count++;
		
    			if(count == 2){
    				for(int j = 0; j< len; ++j){
    					System.out.println(0);
    				}
    				return;
    			}
		
    			continue;
    		}
    		product *= i;
    	}

	
    	for(int i : input)
    	{
    		if(count == 1){
    			if(i == 0){
    				System.out.println(product);
    				continue;
    			}
    			else{
    				System.out.println(0);
    				continue;
    			}
    		}
    		else
    			System.out.println(product/i);
    	}

    }
}

class Arr {
    public static void prodOther(int[] a) {
        int p = 1;
        for (int entry : a) {
            if (entry != 0) {
                p *= entry;
            }
        }
        for (int i = 0; i < a.length; ++i) {
            a[i] = a[i] == 0 ? 0 : p / a[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 3, 4};
        prodOther(a);
        for (int e : a) {
            System.out.println(e);
        }
    }
}

public static long generateProduct(int[] arr){
long product = 1;
int zeros;
for(int a : arr){
if(a == 0){
zeros ++;
if(zeros > 1){
return 0;
}
}else{
product *= a;
}
}
return product;
}
public static void main(String args[]){
int[] arr = new int[] {1,2,3,4};
long product = generateProduct();
for(int a : arr){
System.out.println(product/a);
}
}

In Python:

def missing_product(ints):
    product = reduce(lambda x,y: x*y, ints)
    return [product / i for i in ints]

public static int[] calculateSpecialZero(int[] array) {
        int total = 1;
        boolean zeroSeen = false;
        for(int i = 0; i < array.length; i++) {
            if(array[i] == 0) {
                zeroSeen = true; // do not record it in out total
            } else {
                total *= array[i];
            }
        }
        // now we have total we can replace array values
        for(int j = 0; j < array.length; j++) {
            if(zeroSeen) {
                if(array[j] == 0) {
                    array[j] = total;
                } else {
                    array[j] = 0;
                }
            } else {
                array[j] = total / array[j];
            }
        }
        return array;
    } // O(N) with only O(1) space

Here is C++ solution...

#include<iostream>
using namespace std;

void printProduct(int* arr, int n){
	if (n <= 0)
		return;

	int product = 1;
	int zero = 0;
	for (int i = 0; i < n; ++i){
		if (!arr[i])
			zero++;
		else
			product *= arr[i];
	}

	if (zero>1){
		for (int i=0; i < n; ++i)
			cout << 0 << " ";
	}
	else if (zero == 1){
		for (int i = 0; i < n; ++i)
			if(!arr[i])
				cout << product << " ";
			else
				cout << 0 << " ";
	}
	else{
		for (int i = 0; i < n; ++i)
			cout << product/arr[i] << " ";
	}
	cout << endl;
}

int main(){
	int arr[5] = { 5, 1, 0, 3, 0};
	printProduct(arr, 5);
	return 0;
}

def genRand(num):
    b = 1
    result = []
    for i in range(len(num)):
        for j in range(len(num)):
            if j != i:
                b *= num[j]
        result.append(b)
        b = 1
    return result

def get_ans(array):                                          
    result=[1]*len(array)                                    
    for i in range(len(array)-2,-1,-1):                      
        result[i]=result[i+1]*array[i+1]                     
                                                             
    left=1                                                   
    for j in range(0,len(array)):                            
        result[j] *=left;                                    
        left *= array[j]                                     
                                                             
    print(result)                                            
                                                             
arra=[10, 4, 1, 6, 2]                                        
                                                             
get_ans(arra)

def get_ans(array):  
		result=[1]*len(array)                
		for i in range(len(array)-2,-1,-1):  
    			result[i]=result[i+1]*array[i+1] 
                                     
		left=1                               
		for j in range(0,len(array)):        
    			result[j] *=left;                
    			left *= array[j]                 
                                     
		print(result)

Wrong answer by everyone!!!