使用 C++ 令数组中的所有元素都可被 4 整除的最小步数

问题陈述

给定一个大小为 n 的数组，任务是找出使数组中所有元素都可被 4 整除所需的最小步数。一步的定义是：从数组中移除任意两个元素，并把这两个元素的和添加到数组中

示例

如果输入数组为{1, 2, 0, 2, 4, 3}，那么需要 3 个操作−

1 + 3 = 4
2 + 2 = 4
0 + 4 = 4

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

算法

1. Sum of all the elements of the array should be divisible by If not, this task is not possible
2. Initialize an array namely modulus of size 4 to 0
3. Initialize a counter to 0. It will keep track of number of steps done
4. Traverse through the input array and take modulus 4 of each element
5. Increment the value of the mod 4 value in the modulus array by 1
6. modulus[0] is the count of elements that are already divisible by 4. So no need to pair them with any other element
7. modulus[1] and modulus[3] elements can be combined to get a number divisible by 4. So, increment count to the minimum value of the both
8. Every 2 elements of modulus[2] can be combined to get an element divisible to 4.
9. For the remaining elements, increment value modulus[2] by half of modulus[1] and modulus[3].
10. Now, increment count by half modulus[2]. We take half because every two elements are combined as one
11. The final value of count is the number of steps required to convert the all the elements of the input array divisible by 4

示例

在线演示

#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(int arr[], int n) {
   int count = 0;
   int modulus[4] = {0};
   int sum = 0;
   for (int i = 0; i < n; i++) {
      int mod = arr[i] % 4;
      sum += mod;
      modulus[mod]++;
   }
   if (sum % 4 != 0) {
      return -1;
   } else {
      if (modulus[1] > modulus[3]) {
         count += modulus[3];
      }
      else {
         count += modulus[1];
      }
      modulus[1] -= count;
      modulus[3] -= count;
      modulus[2] += modulus[1] / 2;
      modulus[2] += modulus[3] / 2;
      count += modulus[1] / 2;
      count += modulus[3] / 2;
      count += modulus[2] / 2;
      return count;
   }
}
int main() {
   int arr[] = {1, 2, 0, 2, 4, 3};
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << "Minimum required steps = " << getMinRequiredSteps(arr, n) << endl;
   return 0;
}

当你编译并执行上述程序时，它会生成如下的输出

输出

Minimum required steps = 2

更新日期： 2019-12-23

408 浏览量

开启您的职业生涯

完成课程获得认证

开始
广告