資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究使用 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
更新日期： 2019-12-23
408 瀏覽量
廣告