akbhairwal

Posted on Sep 25, 2019

6-10PM challenge problem #002

#challenge #programming #problem #interview

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

Top comments (7)

EarlWare • Sep 26 '19

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 • Sep 27 '19

Your solution is O(n²⁾ time complexity. You should try for more optimized solution.

EarlWare • Sep 27 '19

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 • Sep 30 '19

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 • Sep 30 '19

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 • Oct 1 '19

you could optimize this solution for O(n)

Mohamed amin Dahwathi • Oct 1 '19

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

DEV Community

6-10PM challenge problem #002

Top comments (7)

Read next

Is WebForms Core the Most Important Web Technology in 2024?

How to visualize bar chart with react-chart-2, showing label on the bar

2290. Minimum Obstacle Removal to Reach Corner

Mastering TypeScript Core Utility Types