Sum of Array after k operations

Question

I got an interview question where I need to do k operation on an array and get the sum of final array.

For each iteration, any random element needs to be picked, divide it by 2 and replace the the value with existing value in array.

arr = [20,10,7]

Pick 7, divide it by 2 and replace 7 with ceil value of the result , output for first iteration will be

[20,10,4]

I wrote the code which is working fine but apparently it is not an optimal solution. It is taking a lot of time for large input.I found a few solutions on stack overflow in other languages but not in iOS related languages.

How can I achieve an optimal solution?

    func minimumSum(numbers:[Int] , iterations:Int) -> Int {
    var arr = numbers
    guard  arr.count > 1 else{
        return 0
    }

    var count = 0
    repeat{
        if let randomNumber = arr.max(){
           // print(randomNumber)
            let divided:Int = Int((Double(randomNumber) / 2).rounded())
            let indexOfNumber = arr.firstIndex(of: randomNumber)
            arr[indexOfNumber!] = divided
            count = count + 1
            print(count)
        }
    }while count < iterations

    return arr.reduce(0,+)


}

For some reason randomNumber wasnt working for me. so i tried with the maximum number — iOSDev, Dec 29 '20 at 00:19

Sweeper · Accepted Answer · 2020-12-29T01:41:12.023

2

One significant thing that slows your code down is that in each iteration, you are finding the maximum of the array, and searching for the index of the maximum using firstIndex(of:). These are all operations that takes longer as the array gets longer.

You wouldn't have to do these things if you were actually finding a random number from the array. You would just find a random index of the array, and get the number at that index, and since you have the index already, you don't have to use firstIndex(of:).

func minimumSum(numbers:[Int] , iterations:Int) -> Int {
    var arr = numbers
    for _ in 0..<iterations {
        guard let randomIndex = arr.indices.randomElement() else {
           return 0
        }
        let randomNumber = numbers[randomIndex]
        let divided = (randomNumber + 1) / 2
        arr[randomIndex] = divided
    }
    return arr.reduce(0,+)
}

edited Dec 29 '20 at 01:41

answered Dec 29 '20 at 00:26

Sweeper

213,210
22
193
313

This is pretty similar to what I was gonna suggest except the calculation. `number / 2 + (number.isMultiple(of: 2) ? 0 : 1)` I was about to post `var numbers = numbers` `(0.. – Leo Dabus Dec 29 '20 at 00:31
1

@LeoDabus, why not `numbers[index] = (number + 1) / 2` ? – vacawama Dec 29 '20 at 01:39
@vacawama Ah I knew there's a trick like that, but I just couldn't come up with it! Thanks! – Sweeper Dec 29 '20 at 01:41
Thanks a lot. though I am not getting the intended output. My actual issue about time got resolved greatly. – iOSDev Dec 29 '20 at 01:46
@vacawama another option is `number / 2 + number % 2` – Leo Dabus Dec 29 '20 at 01:48
1

@LeoDabus, yes that works also, but is 3 operations instead of 2. – vacawama Dec 29 '20 at 01:49
@vacawama yes but that ```number / 2 + number % 2``` also works for negative numbers, to make your ```( number + 1 ) / 2``` work for negatives you also need to add one more operation e.g. ```( number >= 0 ? ( number + 1 ) : ( number - 1 ) ) / 2``` – skaak Dec 29 '20 at 12:29
@skaak, that's a good point with negative numbers. `n / 2 + n % 2` does give the same results as `Int((Double(n) / 2).rounded())` which is OP's formula. – vacawama Dec 29 '20 at 13:39
@skaak, that might still be the incorrect result if the original problem specified to divide by 2 and take the `ceil`, because `ceil(-0.5)` is `0`, not `-1`. – vacawama Dec 29 '20 at 13:44
@vacawama yes I assume here it is normal round away from 0 and have only the OP example 7 / 2 = 4 to go by. I was wondering how you'd do this if e.g. it was divide 3 or 4 or ... then I noted how sign might influence the outcome. I think at some lower level you should be able to use just 2 operations e.g. if you shift bits or have access to C's ```div``` or maybe there is some clever way that we are all missing here. Maybe ```( number + signum( number ) ) / 2``` is the way to go? Then it only works for 2 but you could easily fix that. – skaak Dec 29 '20 at 14:06
1

@vacawama wait that actually does not work - how about ```( n + n.signum() * d / 2 ) / d``` and for performance you can precompute the ```d/2``` – skaak Dec 29 '20 at 15:53
1

@vacawama also + 1 before division would overflow when used with integer max. There is a good [post](https://stackoverflow.com/a/926806/2303865) about this from Eric Lippert – Leo Dabus Dec 31 '20 at 02:09
@vacawama https://gist.github.com/leodabus/a0e0a4f31f019b99e5f2026c5b17cc5c – Leo Dabus Dec 31 '20 at 02:19

Sum of Array after k operations

1 Answers1