C++에서 배열의 합이 짝수가 되도록 추가해야 하는 최소 숫자 구하기

숫자들로 이루어진 배열이 있다고 가정해 봅시다. 우리는 배열 요소들의 합을 짝수로 만들기 위해 최소한 얼마의 숫자를 더해야 하는지 구해야 합니다. 단, 추가하는 숫자는 반드시 0보다 커야 한다는 조건이 있습니다.

따라서 로직은 매우 간단합니다. 요소들의 합이 홀수라면 1을 더해서 짝수로 만들고, 합이 이미 짝수라면 조건(0보다 큰 수)을 만족하기 위해 2를 더해 짝수 상태를 유지합니다.

알고리즘

addMinNumber(arr)

begin
   s := 0
   for each element e from arr, do
      s := e + s
   done
   if s is even, then return 2, otherwise 1
end

즉, 먼저 배열의 모든 요소를 순회하며 전체 합을 계산한 뒤, 그 합이 짝수인지 홀수인지 판별하여 결과를 반환합니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int addMinNumber(int arr[], int n) {
   int sum = 0;
   for(int i = 0; i<n; i++) {
      sum += arr[i];
   }
   return (sum % 2)? 1 : 2;
}
main() {
   int arr[] = {5, 8, 4, 7, 5};
   int n = sizeof(arr)/sizeof(arr[0]);
   cout << "Minimum " << addMinNumber(arr, n) << " should be added";
}

출력 결과

Minimum 1 should be added

동작 원리 설명

위 예제에서 배열 {5, 8, 4, 7, 5}의 합은 5 + 8 + 4 + 7 + 5 = 29로 홀수입니다. 따라서 함수는 1을 반환하여, 1을 더하면 합이 30이 되어 짝수가 됩니다.

만약 배열의 합이 이미 짝수였다면, 0을 더할 수 없으므로(0보다 커야 하는 조건) 가장 작은 양의 짝수인 2를 더하게 됩니다. 이 알고리즘의 시간 복잡도는 배열을 한 번만 순회하므로 O(n)이며, 공간 복잡도는 O(1)입니다.