Minimum Numbers of Function Calls to Make Target Array

  • 时间:2020-09-07 12:13:31
  • 分类:网络文摘
  • 阅读:76 次

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) —

推荐阅读:
保健食品广告九成以上虚假违法  生吃鸡蛋易引起沙门氏菌食物中毒  由副溶血弧菌污染引起的食物中毒  肉毒中毒是一种极为严重的食物中毒  绿色食品与有机食品的联系和区别  盘点人体需要的11种膳食营养补充剂  食品安全事件:商家无良心消费不放心  食药总局启动《食品安全法》修订工作  炎炎夏日怎样选择冰棍雪糕更安全?  问题“毒皮蛋”再引食品安全大讨论 
评论列表
添加评论