Range Queries for finding the Sum of all even parity numbers
Given Q queries where each query consists of two numbers L and R which denotes a range [L, R]. The task is to find the sum of all Even Parity Numbers lying in the given range [L, R].
Parity of a number refers to whether it contains an odd or even number of 1-bits. The number has Even Parity if it contains even number of 1-bits.
Examples:
Input: Q = [ [1, 10], [121, 211] ]
Output:
33
7493
Explanation:
binary(1) = 01, parity = 1
binary(2) = 10, parity = 1
binary(3) = 11, parity = 2
binary(4) = 100, parity = 1
binary(5) = 101, parity = 2
binary(6) = 110, parity = 2
binary(7) = 111, parity = 3
binary(8) = 1000, parity = 1
binary(9) = 1001, parity = 2
binary(10) = 1010, parity = 2
From 1 to 10, 3, 5, 6, 9 and 10 are the Even Parity numbers. Therefore the sum is 33.
From 121 to 211 the sum of all the even parity numbers is 7493.Input: Q = [ [ 10, 10 ], [ 258, 785 ], [45, 245], [ 1, 1000]]
Output:
10
137676
14595
250750
Approach:
The idea is to use a Prefix Sum Array. The sum of all Even Parity Numbers till that particular index is precomputed and stored in an array pref[] so that every query can be answered in O(1) time.
- Initialise the prefix array pref[].
- Iterate from 1 to N and check if the number has even parity or not:
- If the number is Even Parity Number then, the current index of pref[] will store the sum of Even Parity Numbers found so far.
- Else the current index of pref[] is same as the value at previous index of pref[].
- If the number is Even Parity Number then, the current index of pref[] will store the sum of Even Parity Numbers found so far.
- For Q queries the sum of all Even Parity Numbers for range [L, R] can be calculated as follows:
sum = pref[R] - pref[L - 1]
Below is the implementation of the above approach
C++
// C++ program to find the sum // of all Even Parity numbers // in the given range #include <bits/stdc++.h> using namespace std; // pref[] array to precompute // the sum of all Even // Parity Numbers int pref[100001] = { 0 }; // Function that returns true // if count of set bits in // x is even int isEvenParity( int num) { // Parity will store the // count of set bits int parity = 0; int x = num; while (x != 0) { if (x & 1) parity++; x = x >> 1; } if (parity % 2 == 0) return num; else return 0; } // Function to precompute the // sum of all even parity // numbers upto 100000 void preCompute() { for ( int i = 1; i < 100001; i++) { // isEvenParity() // return the number i // if i has even parity // else return 0 pref[i] = pref[i - 1] + isEvenParity(i); } } // Function to print sum // for each query void printSum( int L, int R) { cout << (pref[R] - pref[L - 1]) << endl; } // Function to print sum of all // even parity numbers between // [L, R] void printSum( int arr[2][2], int Q) { // Function that pre computes // the sum of all even parity // numbers preCompute(); // Iterate over all Queries // to print sum for ( int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } } // Driver code int main() { // Queries int N = 2; int Q[2][2] = { { 1, 10 }, { 121, 211 } }; // Function that print // the sum of all even parity // numbers in Range [L, R] printSum(Q, N); return 0; } |
Java
// Java program to find the sum // of all Even Parity numbers // in the given range import java.io.*; import java.util.*; class GFG { // pref[] array to precompute // the sum of all Even // Parity Numbers static int [] pref = new int [ 100001 ]; // Function that returns true // if count of set bits in // x is even static int isEvenParity( int num) { // Parity will store the // count of set bits int parity = 0 ; int x = num; while (x != 0 ) { if ((x & 1 ) == 1 ) parity++; x = x >> 1 ; } if (parity % 2 == 0 ) return num; else return 0 ; } // Function to precompute the // sum of all even parity // numbers upto 100000 static void preCompute() { for ( int i = 1 ; i < 100001 ; i++) { // isEvenParity() // return the number i // if i has even parity // else return 0 pref[i] = pref[i - 1 ] + isEvenParity(i); } } // Function to print sum // for each query static void printSum( int L, int R) { System.out.println(pref[R] - pref[L - 1 ]); } // Function to print sum of all // even parity numbers between // [L, R] static void printSum( int arr[][], int Q) { // Function that pre computes // the sum of all even parity // numbers preCompute(); // Iterate over all Queries // to print sum for ( int i = 0 ; i < Q; i++) { printSum(arr[i][ 0 ], arr[i][ 1 ]); } } // Driver code public static void main(String[] args) { // Queries int N = 2 ; int [][] Q = { { 1 , 10 }, { 121 , 211 } }; // Function that print // the sum of all even parity // numbers in Range [L, R] printSum(Q, N); } } // This code is contributed by coder001 |
Python3
class GFG : # pref[] array to precompute # the sum of all Even # Parity Numbers pref = [ 0 ] * ( 100001 ) # Function that returns true # if count of set bits in # x is even @staticmethod def isEvenParity( num) : # Parity will store the # count of set bits parity = 0 x = num while (x ! = 0 ) : if ((x & 1 ) = = 1 ) : parity + = 1 x = x >> 1 if (parity % 2 = = 0 ) : return num else : return 0 # Function to precompute the # sum of all even parity # numbers upto 100000 @staticmethod def preCompute() : i = 1 while (i < 100001 ) : # isEvenParity() # return the number i # if i has even parity # else return 0 GFG.pref[i] = GFG.pref[i - 1 ] + GFG.isEvenParity(i) i + = 1 # Function to print sum # for each query @staticmethod def printsum( L, R) : print (GFG.pref[R] - GFG.pref[L - 1 ]) # Function to print sum of all # even parity numbers between # [L, R] @staticmethod def printSum( arr, Q) : # Function that pre computes # the sum of all even parity # numbers GFG.preCompute() # Iterate over all Queries # to print sum i = 0 while (i < Q) : GFG.printsum(arr[i][ 0 ], arr[i][ 1 ]) i + = 1 # Driver code @staticmethod def main( args) : # Queries N = 2 Q = [[ 1 , 10 ], [ 121 , 211 ]] # Function that print # the sum of all even parity # numbers in Range [L, R] GFG.printSum(Q, N) if __name__ = = "__main__" : GFG.main([]) # This code is contributed by aadityaburujwale. |
C#
// C# program to find the sum // of all Even Parity numbers // in the given range using System; class GFG { // pref[] array to precompute // the sum of all Even // Parity Numbers static int [] pref = new int [100001]; // Function that returns true // if count of set bits in // x is even static int isEvenParity( int num) { // Parity will store the // count of set bits int parity = 0; int x = num; while (x != 0) { if ((x & 1) == 1) parity++; x = x >> 1; } if (parity % 2 == 0) return num; else return 0; } // Function to precompute the // sum of all even parity // numbers upto 100000 static void preCompute() { for ( int i = 1; i < 100001; i++) { // isEvenParity() // return the number i // if i has even parity // else return 0 pref[i] = pref[i - 1] + isEvenParity(i); } } // Function to print sum // for each query static void printSum( int L, int R) { Console.WriteLine(pref[R] - pref[L - 1]); } // Function to print sum of all // even parity numbers between // [L, R] static void printSum( int [,] arr, int Q) { // Function that pre computes // the sum of all even parity // numbers preCompute(); // Iterate over all Queries // to print sum for ( int i = 0; i < Q; i++) { printSum(arr[i, 0], arr[i, 1]); } } // Driver code public static void Main() { // Queries int N = 2; int [,] Q = { { 1, 10 }, { 121, 211 } }; // Function that print // the sum of all even parity // numbers in Range [L, R] printSum(Q, N); } } // This code is contributed by AbhiThakur |
Javascript
<script> // Javascript program to find the sum // of all Even Parity numbers // in the given range // pref[] array to precompute // the sum of all Even // Parity Numbers let pref = new Array(100001).fill(0); // Function that returns true // if count of set bits in // x is even function isEvenParity(num) { // Parity will store the // count of set bits let parity = 0; let x = num; while (x != 0) { if (x & 1 == 1) parity++; x = x >> 1; } if (parity % 2 == 0) return num; else return 0; } // Function to precompute the // sum of all even parity // numbers upto 100000 function preCompute() { for (let i = 1; i < 100001; i++) { // isEvenParity() // return the number i // if i has even parity // else return 0 pref[i] = pref[i - 1] + isEvenParity(i); } } // Function to print sum // for each query function printSum2(L, R) { document.write(pref[R] - pref[L - 1] + "<br>" ); } // Function to print sum of all // even parity numbers between // [L, R] function printSum(arr, Q) { // Function that pre computes // the sum of all even parity // numbers preCompute(); // Iterate over all Queries // to print sum for (let i = 0; i < Q; i++) { printSum2(arr[i][0], arr[i][1]); } } // Driver code // Queries let N = 2; let Q = [[1, 10], [121, 211]]; // Function that print // the sum of all even parity // numbers in Range [L, R] printSum(Q, N); // This code is contributed by _saurabh_jaiswal. </script> |
33 7493
Time Complexity: O(Q*log(N)), where n is the size of the array and Q is the number of queries.
Auxiliary Space: O(1)
Contact Us