Minimum Numbers of Function Calls to Make Target Array

  • Time:2020-09-07 12:13:31
  • Class:Weblog
  • Read:29

Consider the following function to make changes to an array of numbers:

1
2
3
4
5
6
7
8
9
10
11
func modify(arr, op, idx) {
  // add by 1 index idx
  if (op == 0) {
    arr[idx] ++;
  } else if (op == 1) {
    // multiply by 2 to all elements
    for (i = 0; i < arr.length; i ++) {
       arr[i] *= 2;
    }
  }
}
func modify(arr, op, idx) {
  // add by 1 index idx
  if (op == 0) {
    arr[idx] ++;
  } else if (op == 1) {
    // multiply by 2 to all elements
    for (i = 0; i < arr.length; i ++) {
       arr[i] *= 2;
    }
  }
}

Your task is to form an integer array nums from an initial array of zeros arr that is the same size as nums. Return the minimum number of function calls to make nums from arr. The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:
Input: nums = [1,5]
Output: 5
Explanation: Increment by 1 (second element): [0, 0] to get [0, 1] (1 operation).
Double all the elements: [0, 1] -> [0, 2] -> [0, 4] (2 operations).
Increment by 1 (both elements) [0, 4] -> [1, 4] -> [1, 5] (2 operations).
Total of operations: 1 + 2 + 2 = 5.

Example 2:
Input: nums = [2,2]
Output: 3
Explanation: Increment by 1 (both elements) [0, 0] -> [0, 1] -> [1, 1] (2 operations).
Double all the elements: [1, 1] -> [2, 2] (1 operation).
Total of operations: 2 + 1 = 3.

Example 3:
Input: nums = [4,2,5]
Output: 6
Explanation: (initial)[0,0,0] -> [1,0,0] -> [1,0,1] -> [2,0,2] -> [2,1,2] -> [4,2,4] -> [4,2,5](nums).

Example 4:
Input: nums = [3,2,2,4]
Output: 7

Example 5:
Input: nums = [2,4,8,16]
Output: 8

Constraints:
1 <= nums.length <= 10^5
0 <= nums[i] <= 10^9

Hints:
Work backwards: try to go from nums to arr.
You should try to divide by 2 as much as possible, but you can only divide by 2 if everything is even.

Math Algorithm to Compute the Minimum Numbers of Function Calls to Make Target Array

Let’s consider the change backwards. If a number is odd, we can only decrement by one. Otherwise, for even numbers, we only need to divide them the maximum number of times.

The final answer is the operation required for both Multiplication and Addition. The complexity is O(NLogM) where N is the number of the elements in the array and the M is the average for those numebrs. The following is the Python Implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        add = 0
        mul = 0
        for n in nums:
            m = 0
            while n > 0:                
                if (n & 1) == 1:
                    add += 1
                    n -= 1
                else:
                    m += 1
                    mul = max(m, mul)
                    n //= 2
        return add + mul
class Solution:
    def minOperations(self, nums: List[int]) -> int:
        add = 0
        mul = 0
        for n in nums:
            m = 0
            while n > 0:                
                if (n & 1) == 1:
                    add += 1
                    n -= 1
                else:
                    m += 1
                    mul = max(m, mul)
                    n //= 2
        return add + mul

And the C++ implementation is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minOperations(vector<int> nums) {
        int add = 0, mul = 0;
        for (auto &n: nums) {
            int m = 0;
            while (n) {
                if ((n & 1) == 1) {
                  ++ add;
                  -- n;
                } else {
                  ++ m;
                  n >>= 1;
                }
            }
            mul = max(mul, m);
        }
        return add + mul;
    }
};
class Solution {
public:
    int minOperations(vector<int> nums) {
        int add = 0, mul = 0;
        for (auto &n: nums) {
            int m = 0;
            while (n) {
                if ((n & 1) == 1) {
                  ++ add;
                  -- n;
                } else {
                  ++ m;
                  n >>= 1;
                }
            }
            mul = max(mul, m);
        }
        return add + mul;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

Recommend:
5 Skills All Successful Content Writers Have Mastered
Blogging for Dummies in 2019: The Only Cheat Sheet You Need
Are Readers Reaching Your Call To Action?
How to Manage a Content Marketing Plan for Your Blog
4 Simple Techniques To Bring Your Dead Blog Back To Life
How to Earn Bitcoin Through Blogging
5 PayPal Alternatives for Bloggers and Solopreneurs
Can WordPress Make Other E-commerce Platforms Obsolete?
How to Start a Food Blog (A Step-By-Step 2019 Guide)
3 Possible Solutions to the Most Common Corporate Blogging Probl
Share:Facebook Twitter
Comment list
Comment add