Given an array arr[], the task is to calculate the sum of the elements from the given array which has even parity i.e. the number of set bits is even using bitwise operator.
Examples:
Input: arr[] = {2, 4, 3, 5, 9}
Output: 17
Only 3(0011), 5(0101) and 9(1001) have even parity
So 3 + 5 + 9 = 17Input: arr[] = {1, 5, 4, 16, 10}
Output: 15
Approach: Initialize a variable sum = 0 and traverse the array from 0 to n – 1 while counting the number of set bits in arr[i] using Brian Kernighan’s Algorithm. If the count is even then update sum = sum + arr[i]. Print the sum in the end.
Below is the implementation of the above approach:
C++
// C++ program to find the sum of the elements// from an array which have even parity#include <bits/stdc++.h>using namespace std;// Function that returns true if x has even paritybool checkEvenParity(int x){ // We basically count set bits int parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false;}// Function to return the sum of the elements// from an array which have even paritylong sumlist(int a[], int n){ long sum = 0; for (int i = 0; i < n; i++) { // If a[i] has even parity if (checkEvenParity(a[i])) sum += a[i]; } return sum;}// Driver codeint main(){ int arr[] = { 2, 4, 3, 5, 9 }; int n = sizeof(arr) / sizeof(arr[0]); cout << sumlist(arr, n); return 0;} |
Java
// Java program to find the sum of the elements// from an array which have even parityimport java.io.*;class GFG {// Function that returns true if x has even paritystatic boolean checkEvenParity(int x){ // We basically count set bits int parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false;}// Function to return the sum of the elements// from an array which have even paritystatic long sumlist(int a[], int n){ long sum = 0; for (int i = 0; i < n; i++) { // If a[i] has even parity if (checkEvenParity(a[i])) sum += a[i]; } return sum;}// Driver code public static void main (String[] args) { int arr[] = { 2, 4, 3, 5, 9 }; int n =arr.length; System.out.println(sumlist(arr, n)); }}// This code is contributed by inder_verma.. |
Python3
# Python3 program to find the sum of the elements# from an array which have even parity# Function that returns true if x# has even paritydef checkEvenParity(x): # We basically count set bits parity = 0 while (x != 0): x = x & (x - 1) parity += 1 if (parity % 2 == 0): return True else: return False# Function to return the sum of the elements# from an array which have even paritydef sumlist(a, n): sum = 0 for i in range(n): # If a[i] has even parity if (checkEvenParity(a[i])): sum += a[i] return sum# Driver codeif __name__ == '__main__': arr = [ 2, 4, 3, 5, 9 ] n = len(arr) print(sumlist(arr, n))# This code is contributed by 29AjayKumar. |
C#
// C# program to find the sum of the elements // from an array which have even parity using System ;class GFG { // Function that returns true if x has even parity static bool checkEvenParity(int x) { // We basically count set bits int parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false; } // Function to return the sum of the elements // from an array which have even parity static long sumlist(int []a, int n) { long sum = 0; for (int i = 0; i < n; i++) { // If a[i] has even parity if (checkEvenParity(a[i])) sum += a[i]; } return sum; } // Driver code public static void Main () { int []arr = { 2, 4, 3, 5, 9 }; int n =arr.Length; Console.WriteLine(sumlist(arr, n)); } // This code is contributed by Ryuga} |
PHP
<?php// PHP program to find the sum of the// elements from an array which have // even parity// Function that returns true// if x has even parityfunction checkEvenParity($x){ // We basically count set bits $parity = 0; while ($x != 0) { $x = ($x & ($x - 1)); $parity++; } if ($parity % 2 == 0) return true; else return false;}// Function to return the sum of the elements// from an array which have even parityfunction sumlist($a, $n){ $sum = 0; for ($i = 0; $i < $n; $i++) { // If a[i] has even parity if (checkEvenParity($a[$i])) $sum += $a[$i]; } return $sum;}// Driver code$arr = array( 2, 4, 3, 5, 9 );$n = sizeof($arr);echo sumlist($arr, $n); // This code is contributed by ajit.?> |
Javascript
<script>// Javascript program to find the sum of the elements// from an array which have even parity// Function that returns true if x has even parityfunction checkEvenParity(x){ // We basically count set bits let parity = 0; while (x != 0) { x = x & (x - 1); parity++; } if (parity % 2 == 0) return true; else return false;}// Function to return the sum of the elements// from an array which have even parityfunction sumlist(a, n){ let sum = 0; for(let i = 0; i < n; i++) { // If a[i] has even parity if (checkEvenParity(a[i])) sum += a[i]; } return sum;}// Driver codelet arr = [ 2, 4, 3, 5, 9 ];let n = arr.length;document.write(sumlist(arr, n));// This code is contributed by unknown2108</script> |
Output
17
Time complexity: O(nlogn)
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
