在C ++中使数组的所有元素都能被4整除的最少步骤
问题陈述
给定大小为n的数组，任务是找到使数组的所有元素可被4整除的最少步骤数。步骤定义为从数组中删除任何两个元素，然后将这些元素的总和相加到数组
示例
如果输入数组为{1,2,0,2,4,3}，则需要3个操作-
1 + 3 = 4 2 + 2 = 4 0 + 4 = 4
算法
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
热门推荐
3 祝福语简短的微信
10 幼儿祝福语大全简短贺卡
11 感谢教官文案祝福语简短
12 鼠年同事祝福语简短创意
13 元旦祝福语 简短独特群发
14 妈咪跟我生日祝福语简短
15 给儿子新婚祝福语简短
16 伴娘祝福语长文案简短
17 恭喜高考完祝福语简短
18 生日祝福语送老公简短