For those who feels interested to give it a try, the coding puzzle can be found here.

The puzzle is as follows:

**G**

**iven an array of**

*n*integers where*n*> 1,**nums**

**, return an array**

**output**

**such that**

**output[i]**

**is equal to the product of all the elements of**

**nums**

**except**

**nums[i]**

**.**

And the requirements or challenges are:

1. Solve it

**without division**and in O(*n*).
2. Solve it with constant space complexity.

The following is the solution that I came up with (in Swift). I thought it was the best because it only loops the array once while all other solutions that I found around the web loops the array at least twice. But it doesn't conform to the second requirement about the space complexity because of the recursive call, unfortunately.

Besides, for some odd reason, this solution will generate a runtime error when the array holds more than 34892 elements. I can't seem to find any logic issues in the code so far (If you happen to read this article, please do get in touch if you found any issues within the code). Fyi, I'm using Xcode 7.3 which comes with Swift 2.2. Not sure if it is a compiler issue.

Here is the code:

func productExceptSelf(nums: [Int]) -> [Int] {

func product(inout nums: [Int], _ index: Int, _ leftProduct: Int) -> Int {

let number = nums[index]

if index == nums.count-1 {

nums[index] = leftProduct

return number

}

else {

let rightProduct = product(&nums, index + 1, number * leftProduct)

nums[index] = leftProduct * rightProduct

return rightProduct * number

}

}

var numbers = nums

_ = product(&numbers, 0, 1)

return numbers

}

## No comments:

## Post a Comment