Permanent spatial constraint on interview questions from the SDE array. Doubts in classic interviews

Question

You are given an array [a1 To an], and we need to build another array [b1 To bn], where bi = a1*a2*…*an/ai . you are only allowed to use constant space, and time complexity is O (n). Separation not permitted.

The logic of the solution is quite simple, remove bi from the product to get the result. However, when I was processed to solve this problem, I was trapped. Here are my doubts:

In my opinion, constant space here means, despite the length of the array, the number of variables that I can use should be fixed. This prohibits creating new arrays to solve the problem. Since creating new arrays makes the number of variables different when working with different arrays.

I searched most of the solutions for this online, however all the solutions that I can find created new arrays. So, am I missing something? Any thoughts? Many thanks!

Answer 1

I am going to use array indices from 0 to N-1 because this is how we do things in the hood.

You can rewrite the equation for b _i as follows: b _i = (a ₀ × a ₁ × ⋯ × a _i-1 ) × (a _{i + 1} × a _{i + 2} × ⋯ × a _n-1 ) or more succinctly: b _i = (Π _{j = 0 ⋯ i-1} a _j ) × (Π _{j = i + 1 ⋯ n-1} a _j ).

(In case you are not familiar with it, Π is similar to Σ, but it multiplies the terms instead of adding them. Moreover, these formulas are not quite the same as the formula in your question, since according to the formula your question is, b _i is undefined if a _i is equal to zero. However, I will assume that the goal is to cancel a _i in the numerator and denominator, even if it is zero.)

In any case, you can calculate the left offal (Π _{j = 0 ⋯ i-1} a _j ) step by step by moving the array a from 0 to n-1. You can calculate the correct offal (Π _{j = i + 1 ⋯ n-1} a _j ) by going through array a from n-1 to 0.

So the solution is to use two passes.

First pass from 0 to N-1. For each b[i] specify the product a[j] for 0 <= j < i . This pass sets array b to left offal. It takes O (N) time and constant space for the loop counter.

Second pass from N-1 to 0. Update each b[i] by multiplying it by the product a[j] for i < j < N . Thus, the array b is updated by multiplying each element by the corresponding legal subproduct. It takes O (N) time and constant space for the cycle counter and time.

Here's a Python solution:

 b[0] = 1 for i in range(1, N): b[i] = b[i - 1] * a[i - 1] # Now every b[i] is the product of the a[j] where 0 <= j < i. t = 1 for i in range(N-1, -1, -1): b[i] = b[i] * t t *= a[i] # Now every b[i] is the product of the a[j] where 0 <= j < i # and the a[j] where i < j <= N-1. This is the desired output. 

Answer 2

The requirement of constant space does not prohibit the creation of new arrays. It just means that your algorithm should use the same amount of space every time it runs. Since the question requires you to build a new array, I am going to show a function that does this with constant space and in linear time.

You can still create a new array. Just make sure it is a constant size. The easiest way to do this is to make it as possible as possible. For example, in C ++ you can use

 int* b = new int[UINT_MAX]; 

since the largest index that is used in the array is UINT_MAX. Here is a solution that is both linear time and constant space and if necessary creates a new array.

 int* prod(int *a, int len) { int* b = new int[UINT_MAX]; int tmp = 1; b[0] = 1; for (int i = 1; i < len; i += 1) b[i] = b[i - 1] * a[i - 1]; for (int i = len - 1; i >= 0; i -= 1) { b[i] = b[i] * tmp; tmp *= a[i]; } // for return b; } // prod 

The contract of the function should be to ensure that the size of the new array is the same as the input array (although we secretly know it more). This, of course, is not as effective as calculating it in place, but it is NOT what the question asks (at least the way it was formulated).

Answer 3

Perhaps you can do something like this:

 /* size = size of the original array*/ /* orgArr = the original array with the numbers*/ int i; int temp = 1; int *result = (int *)malloc(sizeof(int) * size); memset(result, 1, size); for(i = 0; i < size; i++) { result[i] = temp; temp *= orgArr[i]; } temp = 1; for(i= n-1; i >= 0; i--) { result[i] *= temp; temp *= OrgArr[i]; } 

Cosmic complexity => O (n) Complexity of time => O (n)

You can make this a constant space using UINT_MAX for the result instead of size.

Answer 4

Consideration of the problem,

• You are given an array [a1 .. an]
• build another array [b1 .. bn], where bi = a1 * a2 * ... * an / ai
• you are only allowed to use constant space and time complexity is O (n)
• Permissions Not Allowed

The naive approach is to use division and calculate everything in place, once,

 #!/bin/env ruby #because I can n = aray.size - 1 prod = 1 0.upto(n) { |x| prod *= aray[x] } 0.upto(n) { |x| bray[x] = (aray[x]==0) ? 0 : prod/aray[x] } 

Note that I used bray [], but could easily just fix the result or replace aray []

But the problem operator does not allow division. Too bad.

So instead we need to maintain the original values ​​by putting the result in bray [], where we project aray [] twice, calculating the product from left to right, and then back from right to left,

 #!/bin/env ruby #because I can aray = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 ] bray = [ ] n = aray.size-1 prod = 1 0.upto(n) { |ndx| bray[ndx] = prod; prod *= aray[ndx]; } prod = 1 n.downto(0) { |ndx| bray[ndx] *= prod; prod *= aray[ndx]; } 

Print the results,

 print "aray:\n"; aray.each_index { |ndx| print "[#{ndx}] #{aray[ndx]}\n" } print "bray:\n"; bray.each_index { |ndx| print "[#{ndx}] #{bray[ndx]}\n" } 

Answer 5

Here is the main part of the program.

Considering

a [i] where i is in the range from 0 to n-1

b [i], where I range from 0 to n-1.

Suppose n = 4 for demonstration purpose

CODE runs HERE

 int count,sum=1; for(count = 0; count < n; count++) { b[count] = sum; sum *= a[count]; } /* 

Loop with score = 0

 b[0] = 1; sum = a[0] 

Loop with score = 1

 b[1] = a[0] sum = a[0] a[1] 

Loop with score = 2

 b[2] = a[0] a[1] sum = a[0] a[1] a[2] 

Loop with score = 3

 b[3] = a[0] a[1] a[2] sum = a[0] a[1] a[2] a[3] -- This sum is not used at all 

At the end of the loop

 b[0] = 1; b[1] = a[0] b[2] = a[0] a[1] b[3] = a[0] a[1] a[2] */ sum = 1; for(count = n-1; count >= 0; count--) { b[count] *= sum; sum *= a[count]; } /* 

At the beginning of LOOP

 b[3] = a[0] a[1] a[2] b[2] = a[0] a[1] b[1] = a[0] b[0] = 1; 

Loop with score = 3

 b[3] = a[0] a[1] a[2] -- multiplied with 1 will lead to the same answer sum = a[3] 

Loop with score = 2

 b[2] = a[0] a[1] a[3] sum = a[3] a[2] 

Loop with score = 1

 b[1] = a[0] a[2] a[3] sum = a[3] a[2] a[1] 

Loop with score = 0

 b[0] = a[1] a[2] a[3] -- Multiplied with 1 will lead to the same answer sum = a[3] a[2] a[1] a[0] -- This sum is not used at all. 

At the end of the loop

 b[0] = a[1] a[2] a[3] b[1] = a[0] a[2] a[3] b[2] = a[0] a[1] a[3] b[3] = a[0] a[1] a[2] 

* /