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