Problem:
Given an array of n integers where n>1, return an array of same size an input array where at every index of the output array should contain the product of all elements in the array except the element at the given index.
Example:
arr[] = {10, 4, 1, 6, 2}
prod[] = {48,120,480,80,240}
Solution:
public int[] product_without_self(int[] arr) {
int[] result = new int[arr.length];
result[result.length-1] = 1;
for(int i=arr.length-2; i>=0; i--) {
result[i] = result[i+1] * arr[i+1];
}
int left = 1;
for(int i=0; i<arr.length; i++) {
result[i] *= left;
left *= arr[i];
}
return result;
}
Time Complexity: O(n)
Space Complexity: O(n)
We need to consider the following 3 cases :
1. If the array contains single zero : Replace the zero with the product of all elements(of course excluding zero) and put zero in remaining places
2. If the array contains multiple zeroes : Replace all array elements with zeroes
3. If the array contains only non-zeros elements.
Generally we forget to handle corner cases.
This problem looks very straight forward in terms of understanding but little tricky while implementing. The solution explained is elegant and covers corner cases also.
I think we can do this also in a different way
Step 1: Check if any element or multiple elements are zero.
If yes, we can handle them as Atul’d mentioned above.
Step2: In all are non zero elements, we can store the product of all the elements in the array in a variable say PRO
Step 3: for every i in the array, divide the PRO by the element number and we get the output array.
i.e
PRO == 1;
for (i=0; i<= len; i++)
PRO = PRO * arr[i];
for (i=0; i<= len; i++)
prod[i] = PRO/arr[i];
# * ———————————————————————————-
# * Title: Product.py
# *
# * Description: A program to calculate the Products of all ints except at index
# *
# * Copyright: Venkatesh Bejjenki © 2017
# *
# * @author Venkatesh Bejjenki
# * ———————————————————————————-
import math
a=[10,5,3,4]
#Test-cases
#a=[-1,5,34,6]
#a=[1,0,4]
#a=[2,0,6,7,0]
#a=[1,7,3,4]
x=0
temp=1
zero_count=0
negative_count=0
for i in a:
if(i!=0):
if(i<0):
negative_count+=1
i=i*(-1)
x=x+math.log(i)
else: zero_count=zero_count+1
b=[]
for i in a:
if(zero_count==0):
if(i<0):
temp=i*(-1)
else:
temp=i
y = x-math.log(temp)
z=int(round(math.exp(y)))
if((negative_count%2==0 and i0)) :
z=z*(-1)
b.append(z)
if((zero_count>1) or (zero_count==1 and i!=0)):
b.append(0)
if(zero_count==1 and i==0):
z=int(round(math.exp(x)))
if(negative_count%2==1):
z=z*(-1)
b.append(z)
print b
My solution considering n numbers are given.
int a[n] = { n numbers };
int finalArray[n];
int prod = 1;
for(int i = 1; i<=n; i++)
{
prod = prod * a[i]; // find prod of all given numbers
}
//second loop. Run through all numbers again and divide the prod with the number
for(int j = 1; j <=n; j++)
{
finalArray[j] = prod/a[j];
}
we will get all elements in final array.
Complexity = O(n)
#include
void main()
{
int n=0;
int a[] = {10, 4, 1, 6, 2};
int finalArray[n];
int prod = 1;
n=4;
for(int i = 0; i<=n; i++)
{
prod = prod * a[i]; // find prod of all given numbers
}
//second loop. Run through all numbers again and divide the prod with the number
for(int j = 0; j <=n; j++)
{
finalArray[j] = prod/a[j];
}
printf("%d\n",prod);
for(int j = 0; j <=n; j++)
{
printf("%d ",finalArray[j]);
}
}
Simplified solution:
#include
void main()
{
int n=0,a[] = {10, 4, 1, 6, 2},finalArray[n], prod = 1;
n=(sizeof(a)/sizeof(int)) – 1;
for(int i = 0; i<=n; i++)
prod = prod * a[i]; // find prod of all given numbers
//second loop. Run through all numbers again and divide the prod with the number
for(int j = 0; j <=n; j++)
finalArray[j] = prod/a[j];
for(int j = 0; j <=n; j++)
printf("%d ",finalArray[j]);
}
Thanks @Shubham
#include
void main()
{
int n=0,a[] = {10, 4, 1, 6, 2}, prod = 1;
n=(sizeof(a)/sizeof(int)) – 1;
for(int i = 0; i<=n; prod *= a[i],i++);
for(int j = 0; j <=n; printf("%d ", prod/a[j]),j++);
}