## DEV Community is a community of 553,164 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# 6-10PM challenge problem #002

Array of Array Products

There is an array 'arr' of Integers of size n, for every index i (from 0 to n) you can calculate product of all element integers except that element.
Solve without using division and analyze your solution’s time and space complexities.

Examples:

input: arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]

input: arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]

Solution

## Discussion

EarlWare

Swift Solution:

``````import Foundation

/*
6-10PM Challenge part 2

@param intArray is a list of Ints which are to be multiplied together
(minus the number in the slot the result goes into).

@return an array where the product of all other elements are at each index.
(ie: [8, 10, 2]  ->  [20, 16, 80]
*/
func arrayOfArrayProducts(intArray:[Int]) -> [Int] {
var newArray = [Int]()

for index in 0..<intArray.count {
//  begin each pass with the multiplicitive indenity so we can just roll all the multiplication together
newArray.append(1)

for searchIndex in 0..<intArray.count {
//  make sure the search index isnt the slot we are currently working on calculating, then roll on the multiplication.
if index != searchIndex {
newArray[index] *= intArray[searchIndex]
}
}
}

return newArray
}

let example1 = [8, 10, 2]
let example2 =  [2, 7, 3, 4]

let solution1 = [20, 16, 80]
let solution2 = [84, 24, 56, 42]

print(example1, " -> ", arrayOfArrayProducts(intArray: example1))
print(example2, " -> ", arrayOfArrayProducts(intArray: example2), "\n\n")

print("All examples match:  ", (arrayOfArrayProducts(intArray: example1) == solution1 &&  arrayOfArrayProducts(intArray: example2) == solution2), "\n")

``````

Output:

``````[8, 10, 2]  ->  [20, 16, 80]
[2, 7, 3, 4]  ->  [84, 24, 56, 42]

All examples match:   true

Program ended with exit code: 0
``````

In the spirit of the last solution: for loops!

akbhairwal

Your solution is O(n2) time complexity. You should try for more optimized solution.

EarlWare

After posting my first solution, I took a look at yours, and now I can't unsee it. So I took some time trying to come up with another creative solution, but in the end, I couldn't figure out anything that was more efficient than what you had posted.

I ran everything I tried through a little repetitive test to see how different approaches stacked up, so here's a quick rundown.

Basic test setup:

``````let testData1 = [8, 10, 2]
let testData2 = [2, 7, 3, 4]
let testData3 = [2, 7, 3, 4, 6, 5, 9, 11, 14, 25, 12, 13, 15, 18, 34, 27]
var result1:[Int] = []
var result2:[Int] = []
var result3:[Int] = []

for _ in 0...5000000 {
result1 = test1(intArray: testData1)
result2 = test1(intArray: testData2)
result3 = test1(intArray: testData3)
}
print(result1, "\n", result2, "\n", result3)
``````

There is definitely a little overhead, but since they all ran through the same setup, I figured at least relatively speaking, the results should still be informative.

And here are the different functions tested:

``````//  Baseline test.  First attempt at coding this challenge,
//   ~5.9sec per 5mil runs on test data.
func test1(intArray:[Int]) -> [Int] {
//  initalize with all values being multiplicitive indenity so we can just roll all the multiplication together
var newArray:[Int] = [Int](repeating: 1, count: intArray.count)

for index in 0..<intArray.count {
for searchIndex in 0..<intArray.count {
//  make sure the search index isnt the slot we are currently working on calculating, then roll on the multiplication.
if index != searchIndex {
newArray[index] *= intArray[searchIndex]
}
}
}

return newArray
}

// Attempted to use some built in array mutating functions and.... TERRRRRIIIIBLE CPU hog.
// ~1.46 MINUTES for 5mil runs on test data.
func test2(intArray:[Int]) -> [Int] {
var result:[Int] = [Int](repeating: 1, count: intArray.count)

for index in 0..<intArray.count {
let tmp = intArray.filter({ \$0 != intArray[index] })
result[index] = tmp.reduce(1, *)
}

return result
}

//  Attempted solution similar to authors, but with only using arrays, then combining the results.
//  ~10 sec per 5mil runs on test data.... fail
func test3(intArray:[Int]) -> [Int] {
// initalize all working arrays with multiplicative identity 1
var forwardPass = [Int](repeating: 1, count: intArray.count)
var reversePass = [Int](repeating: 1, count: intArray.count)
var result      = [Int](repeating: 1, count: intArray.count)

// cumulatively multiply forwards
for index in 1..<intArray.count {
forwardPass[index] = forwardPass[index-1]*intArray[index-1]
}
// cumulatively multiply backwards
for index in (0..<intArray.count-1).reversed() {
reversePass[index] = reversePass[index+1]*intArray[index+1]
}
// multiply the two accumulation arrays together for the final result.
for index in 0..<intArray.count {
result[index] = forwardPass[index]*reversePass[index]
}

return result
}

//  Solution posted by author, adapted to Swift.
//  ~3.15 sec per 5mil runs on test data.  Hands down winner.
func test4(intArray:[Int]) -> [Int] {
var result:[Int] = [Int](repeating: 1, count: intArray.count)
var product = 1

for index in 0..<intArray.count {
result[index] = product
product *= intArray[index]
}

product = 1
for index in (0..<intArray.count).reversed() {
result[index] *= product
product *= intArray[index]
}

return result
}
``````

I also noticed that over the course of 5mil(*3) runs, the overhead difference of creating an empty array and filling it vs initializing an array already of the full size you're going to use is pretty huge. ie:

``````var array1:[Int] = []

for _ 1...50 {
array1.append(1)
}
//  vs
var array2:[Int] = [Int](repeating: 1, count: 50)
``````

test1() dropped from 8.5 sec to about 5.9 sec once I made that small change.

So between that and the revelation about how slow .filter() and .reduce() are in swift, Id say if you're serious about performance, it's going to be super important to really understand what's going on behind the scenes of all these standard libraries we take for granted.

Gab

Clojure solution

Note: This solution is O(n) because `(apply * list)` expands into `(* list0 list1 ... listn)`

``````(defn rest-vec [lst]
"`rest` that returns a vector instead of a list"
(into [] (rest lst)))

(defn array-of-products [arr]
"Calculates product of everything but the first
element and then moves the first element to the end and loops"
(loop [lst arr
time 0
res []]
(if (>= time (count lst))
res
(recur (conj (rest-vec lst) (first lst))
(inc time)
(conj res (apply * (rest lst)))))))

(array-of-products [8 10 2])
;; [20 16 80]
(array-of-products [2 7 4 3])
;; [84 24 42 56]
``````
Mohamed amin Dahwathi

java Sol :

``````public class HelloWorld{

public static void main(String []args){
int[] arr=new int[]{2, 7, 3, 4};
int[] rez=new int[arr.length];
int som=1;
for(int i=0;i<arr.length;i++){
if(i==0){
for(int j=i+1;j<arr.length;j++)
som*=arr[j];
rez[i]=som;
}else{
rez[i]=(som/arr[i])*arr[i-1];
som=rez[i];
}
}

for(int i=0;i<arr.length;i++)
System.out.println(rez[i]);

}
}
``````
akbhairwal

you could optimize this solution for O(n)

Mohamed amin Dahwathi

hello,
i am new but it is O(n) right ? without the last loop ofc