Linkedin Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: Phone Interview
a[]={1,2,0,3,4};
Shouldnt the output be res[]={0,0,24,0,0};
I am not sure why you are ignoring 0 s in your product. Please correct me if I havent understood the question correctly.
Any comments about the limitations imposed due to prod being int? How to exactly put this into words.
Should separate numOfZero == 0 case and numOfZero == 1 case
public class SelfExcludingProduct {
public int[] selfExcludingProduct (int[] input) {
if (input == null)
throw new NullPointerException ("Null input array!");
int[] productArray = new int[input.length];
if (input.length == 0)
return productArray;
int product = 1;
int numOfZeros = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] != 0)
product *= input[i];
else
numOfZeros++;
if (numOfZeros >= 2) {
return productArray;
}
}
for (int i = 0; i < input.length; i++) {
if (numOfZeros == 0) {
productArray[i] = product / input[i];
}
else {
if (input[i] == 0)
productArray[i] = product;
else
productArray[i] = 0;
}
}
return productArray;
}
}
for input : {3, 0, 4, 1}; this code might not work ..output should come as : {0,12,0,0}
but will come out to be diff i.e.{4,12,3,12}
so a little correction here:
public static int[] selfExcludingProduct(int[] input){
int[] result = new int[input.length];
int numberOfZeros = 0;int prod=1;
for(int i=0;i<input.length;i++){
if(input[i]!=0){
prod *=input[i];
}
else{
numberOfZeros++;
}
if(numberOfZeros>=2){
prod = 0;
break;
}
}
for(int i =0;i<input.length;i++){
if(input[i]!=0){
result[i] = prod/input[i];
}
else{
result[i] = prod;
prod = 0;
}
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] arr = {3, 0, 4, 1};
int[] result = selfExcludingProduct(arr);
for(int i:result){
System.out.println(i);
}
}
public int[] selfExcludingProduct(int[] input)
{
int[] output = new int[input.length];
for(int i = 0; i<input.length; i++)
{
int product = 1;
for(int j = 0; j<input.length; j++)
if (j!=i)
product*=input[j];
output[i] = product;
}
return output;
}
Easy.
It can be done in O(n) time.
1) You have to compute the product from the whole array
2) Then the result can be computed in the following way
output[i] = product / input[i]
3) You just have to take care of the corner cases which is zero elements
a) If the array has more then one zero elements then the output will contain only zeros
b) If the array has one zero then the output for the input[i] == 0 is equal product from the remaining elements and the remaining elements are equal 0.
You can check my implementation for better understanding though it was down-voted by someone who misunderstand that solution.
public int [] product(int [] input){
int [] dp = new int [input.length] ;
int [] front = new int [input.length] ;
int [] rear = new int [input.length] ;
front [0] = 1 ;
rear [rear.length - 1] = 1;
for (int i = 1 ; i < front.length ; ++i){
front [i] = front [i - 1] * input [i - 1] ;
}
for (int i = rear.length - 2; i >= 0 ; --i){
rear [i] = rear[i + 1] * input [ i + 1] ;
}
for (int i = 0 ; i < input.length ; ++i){
dp [i] = front [i] * rear [i];
}
return dp;
}
public int [] product(int [] input){
int [] dp = new int [input.length] ;
int [] front = new int [input.length] ;
int [] rear = new int [input.length] ;
front [0] = 1 ;
rear [rear.length - 1] = 1;
for (int i = 1 ; i < front.length ; ++i){
front [i] = front [i - 1] * input [i - 1] ;
}
for (int i = rear.length - 2; i >= 0 ; --i){
rear [i] = rear[i + 1] * input [ i + 1] ;
}
for (int i = 0 ; i < input.length ; ++i){
dp [i] = front [i] * rear [i];
}
return dp;
}
public class SelfExcludingProduct {
public static int[] selfExcludingProduct(int arr[]){
if( arr == null ) return null;
int selfExcludingProduct[] = new int[arr.length];
int leftProduct =1;
selfExcludingProduct[0] = 1;
for(int i =1 ; i < arr.length ; i++){
leftProduct = leftProduct*arr[i-1] ;
selfExcludingProduct[i] =leftProduct;
}
printArray(selfExcludingProduct);
leftProduct =1;
for(int i = arr.length -2 ; i >= 0 ; i--){
leftProduct = leftProduct*arr[i+1] ;
selfExcludingProduct[i] =selfExcludingProduct[i]*leftProduct;
}
printArray(selfExcludingProduct);
return selfExcludingProduct;
}
public static void main(String args[]){
int arr[] ={3, 1, 4, 2,10};
printArray(arr);
selfExcludingProduct(arr);
}
public static void printArray(int arr[]){
if( arr == null ) return ;
for(int i= 0 ; i <arr.length ; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}
}
public static int[] selfExcludingProduct(int[] input) {
if(input == null || input.length == 0)
return null;
int product = 1;
int nonZeroProduct = 1;
int[] prod = new int[input.length];
for(int i : input) {
if(i!=0) {
nonZeroProduct*=i;
}
product*=i;
}
for(int i=0; i< input.length;i++) {
if(input[i] == 0) {
prod[i] = nonZeroProduct;
}
else {
prod[i] = product/input[i];
}
}
return prod;
}
This should cover a case where ONLY one element in array is 0, the self-excluding product of 0 is a non-zero value.
{3,1,4,2,0} ==> {0, 0, 0, 0, 24}
static void Main(string[] args)
{
var input = new List<int>() { 3, 1, 4, 2 };
var results = GetProductsOfAllOthers(input);
Console.WriteLine("input: " + string.Join(", ", input.Select(e => e.ToString()).ToArray()));
Console.WriteLine("output: " + string.Join(", ", results.Select(e => e.ToString()).ToArray()));
Console.ReadLine();
}
static List<int> GetProductsOfAllOthers(List<int> list)
{
int firstZeroIndex = -1;
int product = 1;
for (int i = 0; i < list.Count; ++i)
{
var newProduct = product * list[i];
if (newProduct == 0)
{
if (firstZeroIndex == -1)
{
firstZeroIndex = i;
}
else
{
product = 0;
break;
}
}
else
{
product = newProduct;
}
}
var results = new List<int>();
for (int i = 0; i < list.Count; ++i)
{
if (list[i] == 0 && product != 0)
{
results.Add(product);
}
else if (firstZeroIndex == -1)
{
results.Add(product / list[i]);
}
else
{
results.Add(0);
}
}
return results;
}
only allocate one array instead of two arrays in some of the solutions above. also handles 0.
public int[] selfExcludingProduct(int[] input) {
// implementation...
int [] front = new int[input.length];
front[0] = 1;
for(int i =1;i<front.length;i++){
front[i] = front[i-1]*input[i-1];
}
int temp = 1;
for(int i =front.length-1;i>=0;i--){
front[i] = front[i]*temp;
temp*=input[i];
}
return front;
}
public class ExcludingProductArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = { 3,1,4,0,0 };
selfExcludingProduct(input);
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + " ");
}
}
private static void selfExcludingProduct(int[] input) {
// TODO Auto-generated method stub
int ArrayProduct = 1;
int zeroProduct = 1;
int zeroElementCount = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] != 0 && zeroElementCount < 2) {
zeroProduct *= input[i];
}
if (input[i] == 0) {
zeroElementCount++;
if (zeroElementCount > 1)
zeroProduct = 0;
}
ArrayProduct *= input[i];
}
for (int i = 0; i < input.length; i++) {
if (input[i] == 0)
input[i] = zeroProduct;
else
input[i] = (ArrayProduct / input[i]);
}
}
}
Guys, you are seriously messing this one up. The top answer is 12 lines of code and in O(N^2)
Here's the most elegant solution I can think of in O(n):
def transform(array):
product = reduce( lambda x , y : x * y , array )
return map ( lambda x : product / x, array)
That's it.
For those a little less familiar with map and reduce:
def transform(array):
product = 1
for num in array:
product*=num
return [product/num for num in array]
Mr. Genius, How would your elegant solution handle an array with zeros ?
[2, 3, 4, 0, 7, 8, 0, 1] ??
I used C++ and there are three situations.
1) Two zeros in original array - all entries in the result should be zero
2) One zero in original array - all entries except the one has zero in original array should be zero and the one has zero should has the product value
3) No zero in original array - just use product / arr[i]
int[] fill_product(int arr[]){
int product = 1;
int numOfZeros = 0;
int size = sizeof(arr)/sizeof(arr[0]);
for(int i = 0; i<size; i++){
if(arr[i]==0)
numOfZeros++;
else
product *= arr[i];
if(numOfZeros>1)
break;
}
int result[size];
fill(result,result+size,0);
if(numOfZeros>=2)
return result;
if(numOfZeros==1){
for(int i = 0; i<size; i++){
if(arr[i]==0)
result[i] = product;
}
return result;
}
for(int i = 0; i<size; i++)
result[i] = product / arr[i];
return result;
}
Formatted version:
public static void main(String[] args) {
int prod = 1;
int noOfZeros = 0;
int[] arr = { 3, 0, 0, 2 };
for (int i = 0; i < arr.length; i++) {
if (arr[i] != 0) {
prod *= arr[i];
} else {
noOfZeros++;
if (noOfZeros > 1) {
break;
}
}
}
if (noOfZeros > 1) {
Arrays.fill(arr, 0);
} else {
for (int i = 0; i < arr.length; i++) {
if (noOfZeros == 1) {
if (arr[i] == 0) {
arr[i] = prod;
} else {
arr[i] = 0;
}
} else {
arr[i] = prod / arr[i];
}
}
}
System.out.println(Arrays.toString(arr));
}
- Byll September 17, 2014