Google Interview Question: Given an array of numbers, re... | Glassdoor.co.in

Interview Question

Senior Software Engineer Interview Mountain View, CA (US)

Given an array of numbers, replace each number with the

  product of all the numbers in the array except the number itself *without* using division.
Answer

Interview Answer

34 Answers

7

Create a tree, where the leaf nodes are the initial values in the array.

Interview Candidate on 13-Jul-2009
2

Given array A[1..n]
create array B[1..n]= {1} // all elements =1 ;
for (i=1; ij) B[i] *=A[j];
  }
}
A=B;

husb on 23-Jul-2009
3

To husb:

Your answer will work, but it's O(n^2) solution. Can you do better?

Interview Candidate on 23-Jul-2009
2

Am I missing something? It can't be this easy:

given array[0..n]

int total = 0;
for(int i=0; i<=n; i++)
{ total += array[i]; }

for(int i=0; i<=n; i++)
{
array[i] = total-array[i];
}

Bill on 29-Jul-2009
1

Ah yes.. I was. The question is PRODUCT, not sum. That will teach me to read the question too fast ;)

Bill on 29-Jul-2009
4

Create a tree, where the leaf nodes are the initial values in the array. Build the binary tree upwards with parent nodes the value of the PRODUCT of its child nodes. After the tree is built, each leaf node's value is replaced by the product of all the value of the "OTHER" child node on its path to root. The pseudo code is like this

given int array[1...n]

int level_size = n/2;
while(level_size != 1){//build the tree
      int new_array[1...level_size];
      for ( int i=0; i left = array[i*2]; (and also from child to parent)
           new_array[i] -> right = array[i*2+1]
          new_array[i] = new_array[i] -> right* new_array[i] -> left; (take the product)
      }
      array= new_array;
      level_size /=2;
}

for(int i=0; iparent;
       if( parent->left == node){//find the other node under the parent
          brother = parent->right;
       }
      else{
           brother = parent->left;
       }
        p *= brother;
       node = parent;
    }
    return p;
}

Dr Zhang on 31-Jul-2009
1

btw, it's O(n*logn)

Dr Zhang on 31-Jul-2009
28

It seems to me that for any number array[i], you're looking for

PRODUCT(all array[j] where j i])

we can simply precompute these "running products" first from left-to-right, then right-to-left, storing the results in arrays. So,

leftProduct[0] = array[0];
for j=1; j = 0; j--
  rightProduct[j] = rightProduct[j+1]*array[j];

then to get our answer we just overwrite the original array with the desired product

array[0] = rightProduct[1];
array[n-1] = leftProduct[n-2];
for j=1; j < n-1; j++
  array[j] = leftProduct[j-1] * rightProduct[j+1]

and clearly this solution is O(n) since we just traversed the data 3 times and did a constant amount of work for each cell.

betterStill on 16-Sep-2009
3

betterStill, I think you have the answer the interviewer wanted..

But... if the array is google sized, don't we have to worry about overflows?

Ethelbert on 09-Jan-2011
1

it looks to me can be done in order n time given the following relation:
product[n] = product[n-1]*array[n-1]/array[n]
for example we have array 2 3 4 5 6
product[0]=3*4*5*6
product[1]=2*4*5*6
array[0] = 2;
array[1]=3
product[1]=product[0]*array[0]/array[1]

dadao on 03-Mar-2011
2

Here are my 2 cents to do this in memory without creating temporary arrays. The simple solution , if division was allowed, was multiple all the elements of the array i.e.
tolal = A[0]*A[1]]*....*A[n-1]
now take a loop of array and update element i with A[i] = toal/A[i]
Since division is not allowed we have to simulate it.
If we say X*Y = Z, it means if X is added Y times it is equal to Z e.g.
2*3 = 6, which also means 2+2+2 = 6. This can be used in reverse to find how mach times X is added to get Z. Here is my C solution, which take pointer to array head A[0] and size of array as input

void ArrayMult(int *A, int size)
{
    int total= 1;
    for(int i=0; i< size; ++i)
        total *= A[i];
    for(int i=0; i< size; ++i)
    {
        int temp = total;
        int cnt = 0;
        while(temp)
        {
            temp -=A[i];
            cnt++;
        }
        A[i] = cnt;
    }
}
Speed in O(n) and space is O(1)

narya on 10-Jun-2011
1

narya trick is good but really useful as it might take more iterations depending on values... eg. 2,3,1000000000000000
so if you have 3 numbers and if you are trying for the first one it will go for 500000000000000 iterations, hence as the overall product value wrt to the value matters a lot... try something else....

kiran on 23-Jun-2011
1

narya, your solution is not O(n). You have to also account for how many times you will run through the inner loop - which will be a lot.

You can do it in O(n) time and O(n) space. In one pass, populate B[i] with the product of every number before i. In the second pass, multiply this with the product of every number after i. Can't think of a way to do it without the second array.

void ArrayMult(int *A, int size)
{
  runningProduct = 1;
  int *B = new int[size];

  for(int i = 0; i = 0; --i)
  {
    B[i] *= runningProduct;
    runningProduct *= A[i];
  }

  for(int i = 0; i < size; ++i)
  {
    A[i] = B[i];
  }
}

donutello on 17-Sep-2011
1

<strong>Brutefoce Method : </strong> The brute-force method suggests that if we take each element, multiply all elements and store the product in the array B[i], then it would take O(n^2) time.
<strong>Other Solution : </strong> The other solution to this problem can be we multiply all the elements of the array "A" and store the product in a variable (say product.), and then divide the product by each element, then we will get the desired array. The C code of the solution can be :

#include
int main()
{
int n,i=0;
scanf("%d",&amp;n);
int arr[n];
int brr[n];
int product = 1;
for(i=0;i
This solution will take O(n) time. The space complexity of this solution will be O(1).
If we have particularly given that "We can't use the *DIVISION* operator, then the solution to this problem will be as follows."
polygenelubricants method : Let we have 2 arrays, "A" and "B". Let the length of "A" is 4.
i.e. {A[0],A[1],A[2],A[3]}
Then we will make two arrays (say temp1 and temp2). One array will be storing the product the array before a particular element and temp2 will store the product of elements after a particular element.

temp1 = { 1 , A[0] , A[0]*A[1] , A[0]*A[1]*A[2]}
temp2 = {A[1]*A[2]*A[3] , A[2]*A[3] , A[3] , 1}

And then we will correspondingly multiply temp1 and temp2 and store in B.

B = {A[1]*A[2]*A[3] , A[0*A[2]*A[3] , A[0]*A[1]*A[3] , A[0]*A[1]*A[2]}

The C code to this solution will be :

#include
int main()
{
    int n,i=0;
    scanf("%d",&amp;n);
    int A[n],B[n];
    int temp1[n], temp2[n];
    for(i=0;i=0;i--)
    {
        temp2[i] = product;
        product *= A[i];
    }
    for(i=0;i
The time complexity to this solution will be O(n) and the space complexity to this problem will also be O(n).

Ajay on 06-Jul-2014
2

We can fill two arrays: headProduct and tailProduct. Each headProduct[i] == product of A[0..i-1], tailProduct[i] ==[i+1..A.lenght-1]. They can be built in O(n) and the result could be gathered in O(n). Memory demand is O(n)

eugene on 08-Aug-2015
0

Not commentary

Anonymous on 14-Aug-2015
0

nt a[N] = {1, 2, 3, 4};

int products_below[N];
int products_above[N];

int p=1;
int p1=1;

for (int i=0;i

AT on 12-Oct-2015
0

def solve(arr,n):
    product_arr=[1]*n
    product=1
    for i in xrange(n):
        product_arr[i]*=product
        product*=arr[i]
    product=1
    for i in xrange(n-1,-1,-1):
        product_arr[i]*=product
        product*=arr[i]
    return product_arr

Ravi Shankar on 25-Apr-2016
0

{{{
If A = {a0, a1, a2, ... an}
Construct two arrays called left_p left product and right_p right product:

left_p = {1, a0, a0 * a1, a0 * a1 * a2, .... , a0 * a1 * a2 ... * an-1}
right_p = {a1*a2*...*an, ....... an-2 * an-1 * an , an-1 * an, an , 1}
prod_p[i] = left_p[i] * right_p[i];

}}}

Sravan on 10-May-2016
0

O(N) Solution!!!

    static void Calculate(int[] iArr)
    {
        int total = 1;

        for (int i = 0; i &lt; iArr.Length; i++)
        {
            total *= iArr[i];
        }
        for (int i = 0; i &lt; iArr.Length; i++)
        {
            iArr[i] = (int)(total * (1 / (double)iArr[i]));
        }
    }

Marc on 02-Jun-2016
1

The answer I post above this uses division. Oops. Here is an answer without division

    static void Calculate(int[] iArr)
    {
        int total = 1;

        for (int i = 0; i 0)
            {
                temp -= iArr[i];
                newVal++;
            }
            iArr[i] = newVal;
        }
    }

Marc on 02-Jun-2016
0

Sorry, that last one didn't paste properly

    static void Calculate(int[] iArr)
    {
        int total = 1;

        for (int i = 0; i 0)
            {
                temp -= iArr[i];
                newVal++;
            }
            iArr[i] = newVal;
        }
    }

Marc on 02-Jun-2016
0

p = 1
g = 1
for x in nums:
       g = g* x + p
       p = p + x
return g

kanwar Malik on 04-Jan-2018
0

Way easy with a simple negative exponent

var arr = [2,3,4,5]
var prod = arr.reduce((a,b,arr)=&gt;a*b)
arr.map((x)=&gt;Math.pow(x,-1)*prod)
console.log(arr) //[60,40,30,24]

Christopher R. on 01-Dec-2018
0

I don't know if this is correct. But i think it is. I have done it with python

def multiply(numbers,n):
    total = 1
    for x in numbers:
        if x != n:
            total *= x
    return total
a = [10, 3, 5, 6, 2]
n = 4
prod = []

for i in a:
    re = multiply(a,i)
    prod.append(re)

Jyoti on 17-Jul-2019
0

- create a binary tree with the values of array as leaf node
- each parent is the product of its children
- once the tree is formed, for each value/leaf traverse the tree to the top, each time multiplying the sibling
-if tree construction time is ignored, this will take logn time for each calculation and nlogn time for all elements

Maria W on 18-Dec-2019
0

int[] array = new int[]{2,3,4,5};
    int m = 1;
    int m2 = 1;

    int[] array1 = new int[array.length];
    int[] array2 = new int[array.length];

    for (int i = 0, j = array.length - 1; i &lt; array.length; i++, j--) {
      m *= array[i];
      array1[i] = m;

      m2 *= array[j];
      array2[j] = m2;
    }

    for (int i = 0; i &lt; array.length; i++) {
      if (i == 0) {
        System.out.println(array[i] + " " + m2 / array[i] + " " + array2[i + 1]);
      } else if (i == array.length - 1) {
        System.out.println(array[i] + " " + m2 / array[i] + " " + array1[i - 1]);
      } else {
        System.out.println(array[i] + " " + m2 / array[i] + " " + array1[i - 1] * array2[i + 1]);
      }
    }

Andriy on 22-Apr-2020
0

Of course, if allow more temp arrays it can be done in one iteration
int[] array = new int[]{2, 3, 4, 6};
    int m = 1;
    int m2 = 1;

    int[] array1 = new int[array.length];
    int[] array2 = new int[array.length];
    int[] array3 = new int[array.length];

    int middle = array.length / 2;

    for (int i = 0, j = array.length - 1; i = middle) {
        if (i + 1 != array.length) {
          array3[i] = array1[i - 1] * array2[i + 1];
        } else {
          array3[i] = array1[i - 1];
        }

        if (j - 1 &gt;= 0) {
          array3[j] = array1[j - 1] * array2[j + 1];
        } else {
          array3[j] = array2[j + 1];
        }

      }

    }

    for (int i = 0; i &lt; array.length; i++) {
      System.out.println(array3[i] + "===" + m2 / array[i]);
    }

Andriy on 22-Apr-2020
0

Need help in writing Scala Program for multiplication of 2 elements of array and last element should not exceed 1000.
Input Array:(1,3)
Output: Array(1,3,3,9,27,243...)

Anonymous on 05-May-2020
0

#include
using namespace std;

int main()
{ int y=1,a[23],i,k,s,t,b[76];
    cout &gt;s;
    for(i=0;i&gt;a[i];
    for(i=0;i

C ++ on 13-Jun-2020
0

#include
using namespace std;

int main()
{ int y=1,a[23],i,k,s,t,b[76];
    cout &gt;s;
    for(i=0;i&gt;a[i];
    for(i=0;i

Basics on 13-Jun-2020
0

let arr = [1,2,3,4,5]
arr = arr.map((el,i)=&gt;{
    return arr.slice(0,i).concat(arr.slice(i+1)).reduce((a,b)=&gt;a*b)
})
console.log(arr)

aman khan on 03-Sep-2020
0

traverse once and store all the product of element .
For(0 to n-1)
A[i]= products*pow(a[i],-1);

Anonymous on 01-Oct-2020

One or more comments have been removed.
Please see our Community Guidelines or Terms of Service for more information.

Add Answers or Comments

To comment on this, Sign In or Sign Up.