Minimum Numbers of Function Calls to Make Target Array With Python

EzzEddin Abdullah · 5 mins read ·
python competitiveprogramming

Minimum Numbers of Function Calls to Make Target Array With Python
Minimum Numbers of Function Calls to Make Target Array is problem number 1558 on leetcode and I am going to solve it using Python today.

Understanding the Problem

Minimum Numbers of Function Calls to Make Target Array is a medium problem at leetcode, I hope you have read the problem carefully and have tried solving it. This problem requires you to get the least number of operations that you can do in order to get to the desired array. The question now, how we can do such operations to count its numbers to reach the target array in the least possible way.

Initial thoughts

Let us take this example, having [2, 2] as the target array and we want to know the minimum number of operations to reach that array.

So we start off with [0, 0] adding 1 to each element (2 operations now) reaching [1, 1] and then multiply the whole array by 2 (1 operation) reaching the target array we want [2, 2] so we have 3 operations to reach the desired array for this example as shown below:

Minimum Numbers of Function Calls to Make Target Array With Python
But it’s hard to move from [0, 0] to reach [2, 2] because of the possibility of wrong guessing of the next array we want to reach. What we can better do, is to move backward from [2, 2] to [0, 0] as indicated below:

Minimum Numbers of Function Calls to Make Target Array With Python
In this case, we can divide instead of multiplying and subtracting instead of adding as shown in orange and we’ll end up with the same number of operations.

Better path

So now we have two main operations to be done: division and subtraction. It seems that we use division when all elements in the array are divisible by 2 but what if there is an odd number, we subtract.

The integer division can save us from worrying about the existence of odd numbers because even and odd numbers will be divided and what’s left is the count of operations for every odd number existing which can be done by calculating the remainder. The remainder of any number by 2 is either 1 or 0.

If 1, we indicate that the number is odd and then we know that this is one operation.

Here are some scripts of how that integer division and the remainder are calculated in Python and Javascript:

Python

#!/usr/bin/env python3

#https://leetcode.com/problems/minimum-numbers-of-function-calls-to-make-target-array/

def minfuncalls(nums):
    n = 0
    lennums = len(nums)
    print('>>', n, nums)
    while any(map(lambda e: e!=0, nums)):
        for i in range(lennums):
            n += nums[i] % 2
            nums[i] //= 2
        n += 1
        print('>>', n, nums)
    return n-1 if n > 0 else 0

def test(a,n):
    print(minfuncalls(a) == n, n)

test([0], 0)
test([0,0], 0)
test([0,1], 1)
test([0,2], 2)
test([2,4], 4)
test([1,5], 5)
test([2,2], 3)
test([4,2,5], 6)
test([3,2,2,4], 7)
test([2,4,8,16], 8)

Acknowledgment

The Python code is mutual work with my best friend Nour. He actually has a contribution at gist for explaining a more efficient solution found on leetcode, please see this fantastic gist:‍

Motivated by

About Author

EzzEddin Abdullah
Ezz is a Data Platform Engineer at Affectiva, Electronics and Communications Engineering graduate from Ain Shams University Despite his early career shift, he had two data science internships and now a full-time job in the software industry even after 14 months of military service. Ezz was also active during college, he co-founded Pi; a scientific student activity.

Original Source: Original Post
Please share your Feedback:

Did you enjoy reading or think it can be improved? Don’t forget to leave your thoughts in the comments section below! If you liked this article, please share it with your friends, and read a few more!