BINPARITY - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: mamaleshrh
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

An integer N is said to have even binary parity if the sum of its binary digits is even; and odd binary parity otherwise.

Given N, find its binary parity.

EXPLANATION:

This is really just a pure implementation task, since the statement tells you exactly what needs to be done: find the sum of binary digits of N, and check if this number is even or odd.

Extracting the binary digits of N can be done with a simple loop, similar to how you would get all the digits of a normal (base 10) integer.
That is,

  • Let S denote the sum of binary digits of N. Initially, S = 0.
  • Repeat the following process:
    • If N = 0, stop.
    • Otherwise, extract the last binary digit of N.
      • This is simply the remainder when N is divided by 2, i.e, N % 2.
    • Add this last binary digit to S.
    • Then, divide N by 2 to get rid of this last digit alone, and repeat the process.
      • Note that this division is integer division, which is N/2 in C++/Java and N//2 in Python.

At the end, simply check whether S is even or odd.

In some languages, there are also easier ways with library use.

  • In C++, the __builtin_popcount(n) function returns the number of set bits in the binary representation of n.
  • In Python, bin(n) returns a string denoting the binary representation; so bin(n).count('1') counts the number of ones in it.

TIME COMPLEXITY:

\mathcal{O}(1) per testcase.

CODE:

Editorialist's code 1 (Python) 
for _ in range(int(input())):
    n = int(input())
    par = bin(n).count('1') % 2
    print('Even' if par == 0 else 'Odd')
Editorialist's code 2 (Python) 
for _ in range(int(input())):
    n = int(input())
    s = 0
    while n > 0:
        s += n%2
        n = n//2
    print('Even' if s%2 == 0 else 'Odd')
Editorialist's code 3 (C++) 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int s = __builtin_popcount(n);
        if (s%2 == 0) cout << "Even\n";
        else cout << "Odd\n";
    }
}