CODEWITHSUNDEEP
arraysalgorithmmath
Joey
Joey

Reputation: 219

Pairing elements to obtain maximum number of even sums

Given a circular array of N integers (that is, A[0] and A[N - 1] are adjacent to each other), what's the maximum number of adjacent pairs that you can form whose sum are even? Note that each element can belong to at most one pair.

For example, if we have [5, 7, 9, 6, 3], then you should pair (5, 3) and (7, 9) to achieve the answer of two. Also, if we have [1, 1, 1, 1, 1, 1], then the answer is 3 (pair each adjacent element without wrapping around)

This is a recent problem that I encountered in an interview, and I still can't solve it (I didn't get the job). I know that the sum of two numbers of the same parity produce an even sum (so odd and odd, or even and even), but the whole "wrap-around" part is what's getting me. In particular, I can't figure out whether or not it's optimal to pair a value with its left neighbor or its right neighbor. The current algorithm I'm thinking of is as follows:

This is a wrong algorithm since it fails for [1, 1, 1, 0, 1] in which case it's optimal to pair A[0] with A[n-1] and A[1] with A[2]. Does anyone have any suggestions? I was thinking perhaps something with dynamic programming, but I'm not sure. The circular part is really throwing me off.

Thanks.

Upvotes: 5

Views: 5685

Answers (2)

A K
A K

Reputation: 1

int solution(vector<int> A) {
    int n = A.size();
    
    int ans1 = 0, ans2 = 0;
    {
        vector<int> dp(n, 0);
        for(int i = 1;i<n;i++){
            if((A[i] + A[i-1]) % 2 == 0){
                dp[i] = max(dp[i], 1 + ((i-2>=0)?dp[i-2]:0));
            }
            ans1 = max(ans1, dp[i]);
        }
    }
    {
        A.push_back(A[0]);
        A.erase(A.begin());
        vector<int> dp(n, 0);
        for(int i = 1;i<n;i++){

            if((A[i] + A[i-1]) % 2 == 0){
                dp[i] = max(dp[i], 1 + ((i-2>=0)?dp[i-2]:0));
            }
            ans2 = max(ans2, dp[i]);
        }
    }

    return max(ans1, ans2);
}

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 119877

If all numbers are odd, or all numbers are even, then

  • if array length is even, include all numbers (it doesn't matter how you group).
  • if it is odd, include all numbers except the smallest one.

If there are both odd and even numbers, then you can partition the array into odd runs and even runs. Concatenate the first and the last run if they are both even or both odd. Solve the problem for each run separately. It is easy because the runs are NOT circular. If the length of the run is even, include all numbers. Otherwise, exclude the smallest number at an even position.

This assumes that all numbers are non-negative.

Upvotes: 1

Related Questions