1158-java-sol-by-gayloft.md

Explaining a most efficient Solution for 1558. Minimum Numbers of Function Calls to Make Target Array

The problem: 1558. Minimum Numbers of Function Calls to Make Target Array.

Let's discuss an efficient Java solution by GAYLOFT, rewritten in Python3.

    def minOperations(self, nums: List[int]) -> int:
        addCount = 0
        doubleCount = 0
        for e in nums:
            if e != 0:
                addCount += 1
            elementDoubleCount = 0
            while e > 1:
                elementDoubleCount += 1
                addCount += e % 2
                e //= 2
            doubleCount = max(elementDoubleCount, doubleCount)
        return doubleCount + addCount

First we notice two things: (a) we count op 0 (in addCount) and op 1 (in doubleCount) separately, and (b) the outer loop iterates over the entire list directly.

Let's go into this loop, and initially ignore the first if-block. Let's dissect the while loop with the two surrounding lines:

            elementDoubleCount = 0
            while e > 1:
                elementDoubleCount += 1
                addCount += e % 2
                e //= 2
            doubleCount = max(elementDoubleCount, doubleCount)

The last two statements in the block are the same as ours:

                addCount += e % 2
                e //= 2

The new statement inside the while is:

                elementDoubleCount += 1

But just before the while we have:

            elementDoubleCount = 0

That means that elementDoubleCount counts how many the while was executed, or how many the current element was divided before it reached 1.

Wait! 1? Not 0?

Yes. We'll explain this issue in a moment. But for now, let's just pretend that it's correct. ;)

So, let's take a break from the computer and go to our almighty whiteboard, to see how the next code should be.

Let's have a simple example: [2,4]. What should its doubleCount be?

Let's do all the operations on it and count them:

[2,4]  ; divide all the elements by 2    ; doubleCount becomes 1
[1,2]  ; decrement the 0th element by 1  ; doubleCount remains 1
[0,2]  ; divide all the elements by 2    ; doubleCount becomes 2
[0,1]  ; decrement the 1st element by 1  ; doubleCount remains 2
[0,0]  ; done  => doubleCount is 2

But what is elementDoubleCount for every element of that list? Let's see:

2  ; integer-divide by 2  ; elementDoubleCount becomes 1
1  ; done (we do `while e > 1`)  => elementDoubleCount is 1
---
4  ; integer-divide by 2  ; elementDoubleCount becomes 1
2  ; integer-divide by 2  ; elementDoubleCount becomes 2
1  ; done (we do `while e > 1`)  => elementDoubleCount is 2

So, we can see that we divide each and every element until it reaches one, and the total doubleCount is the largest elementDoubleCount of the elements. (In this case, the elementDoubleCounts of 2 and 4 are 1 and 2, respectively, and the largest of them is 2, which is the doubleCount of [2,4].).

Let's read that part again:

            elementDoubleCount = 0
            while e > 1:
                elementDoubleCount += 1
                addCount += e % 2
                e //= 2
            doubleCount = max(elementDoubleCount, doubleCount)

Yes! Divide until each element reaches one, add to addCount the number of odd numbers encountered while reducing that element to one, and make doubleCount equal to the largest number of integer-division-by-2 operations needed by an element of the list to reach one.

But... but why one? We need to reach zero!

Yes, yes. Let's change the condition to e > 0, and see what happens; read the resulting code first:

            elementDoubleCount = 0
            while e > 0:
                elementDoubleCount += 1
                addCount += e % 2
                e //= 2
            doubleCount = max(elementDoubleCount, doubleCount)

Can you find what's wrong with it?

No? No problem. Let's trace the execution of a simple example. We already now it works until reaching 1, so we test what happens after that:

(eDC is elementDoubleCount, dC = doubleCount, and aC is addCount)

 e | eDC | dC  | aC  | When?
---+-----+-----+-----+------------------
 1 |  0  |  0  |  0  | before the loop
 0 |  1  |  0  |  1  | after the loop
 0 |  1  |  1  |  1  | after max()

Is this what we expect? But first, what we expect?

For 1, we want only a one in addCount. But we ended also with an additional one in elementDoubleCount, which propagated to doubleCount.

So, we stop at 1 in the division loop, and take care of that additional one somewhere else.

How can we take care of that one?

Well, we can do a simple if after the loop to check if the element is one, and increment addCount. But the author of the code we are explaining does something else.

Let's ask ourselves this question: when do we get a one?

Every integer division by 2 ultimately reaches 2, then reaches 1. So, if the element is greater than 1, it will for sure reach one by division.

And if it's one, congratulations, we have already reached our destination!

But if it's zero? No operations are needed at all; we've already reached our destination (for real this time).

So, any non-zero element will definitely need a one in addCount. Later we check how many more are needed while we butcher it into halves.

And we can see that the author does exactly that the first thing when checking an element:

            if e != 0:
                addCount += 1

Now, let's take a look at the entire code again:

    def minOperations(self, nums: List[int]) -> int:
        addCount = 0
        doubleCount = 0
        for e in nums:
            if e != 0:
                addCount += 1
            elementDoubleCount = 0
            while e > 1:
                elementDoubleCount += 1
                addCount += e % 2
                e //= 2
            doubleCount = max(elementDoubleCount, doubleCount)
        return doubleCount + addCount

I hope it's all understandable now.

And... That's all, folks!

I hope it helps. Thank you! :)