Algorithm

A. Beat The Odds
time limit per test
1 second
memory limit per test
256 megabytes
problem link- https://codeforces.com/problemset/problem/1691/A
input
standard input
output
standard output

Given a sequence a1,a2,…,an�1,�2,…,��, find the minimum number of elements to remove from the sequence such that after the removal, the sum of every 22 consecutive elements is even.

Input

Each test contains multiple test cases. The first line contains a single integer t� (1≤t≤1001≤�≤100) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer n� (3≤n≤1053≤�≤105).

The second line of each test case contains n� integers a1,a2,…,an�1,�2,…,�� (1≤ai≤1091≤��≤109) — elements of the sequence.

It is guaranteed that the sum of n� over all test cases does not exceed 105105.

Output

For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every 22 consecutive elements is even.

Example
input
Copy
2
5
2 4 3 6 8
6
3 5 9 7 1 3
output
Copy
1
0
Note

In the first test case, after removing 33, the sequence becomes [2,4,6,8][2,4,6,8]. The pairs of consecutive elements are {[2,4],[4,6],[6,8]}{[2,4],[4,6],[6,8]}. Each consecutive pair has an even sum now. Hence, we only need to remove 11 element to satisfy the condition asked.

In the second test case, each consecutive pair already has an even sum so we need not remove any element.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int t;
  cin>>t;
  while(t--){
    int n;
    cin>>n;
    int eve = 0, odd = 0;
    int x;
    while(n--){
      cin>>x;
      if(x % 2 == 0){
        eve++;
      }
      else{
        odd++;
      }
    }

    cout<<min(odd, eve)<<endl;
  }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
2
5
2 4 3 6 8
6
3 5 9 7 1 3

Output

x
–
+
cmd
1
0
Advertisements

Demonstration

Codeforcess Solution 1691-A A. Beat The Odds ,C++, Java, Js and Python  ,1691-A,Codeforcess Solution

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+