Given an array arr[] of size N and Q queries of the form (L, R), the task is to count number of triplets with even sum for the elements in the range L and R for each query.
Examples:
Input: N = 6, arr[ ] = {1, 2, 3, 4, 5, 6}, Q[ ] = {{1, 3}, {2, 5}}
Output: 1 2
Explanation:
For Query (1, 3): only triplet (1, 2, 3) exists with even sum
For Query (2, 5): Triplets (2, 3, 5) and (3, 4, 5) have even sum.
Hence the output is 1 and 2 respectivelyInput: N = 3, arr[ ] = {1, 2, 5}, Q[ ] = {{1, 2}}
Output: 0
Approach: The above problem can be solved with the observations that for a triplet sum to be even, the elements must be one of the below pattern:
- even + even + even = even
- odd + odd + even = even
Follow the steps below to solve the problem:
- Initialize two arrays, say arr_even[] and arr_odd[] of length size + 1.
- Initialize variables, say even = 0 and odd = 0, to store the count of even and odd numbers.
- Traverse the array arr[] and for each i store even numbers till index i in arr_even[i] and odd numbers till index i in arr_odd[i].
- Iterate over the queries Q[] and for each pair (l, r):
- Find count of even numbers in (l, r) as arr_even[r] – arr_even[l-1] and count of odd numbers in (l, r) as arr_odd[r] – arr_odd[l-1].
- Find count of triplets in variable say ans as sum of (even*(even-1)*(even-2))/6 and (odd*(odd-1)/2)*even.
- Finally, print the ans for each query.
Below is the implementation of the above approach:
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to count number of triplets// with even sum in range l, r for each// queryvoid countTriplets(int size, int queries, int arr[], int Q[][2]){ // Initialization of array int arr_even[size + 1], arr_odd[size + 1]; // Initialization of variables int even = 0, odd = 0; arr_even[0] = 0; arr_odd[0] = 0; // Traversing array for (int i = 0; i < size; i++) { // If element is odd if (arr[i] % 2) { odd++; } // If element is even else { even++; } // Storing count of even and odd // till each i arr_even[i + 1] = even; arr_odd[i + 1] = odd; } // Traversing each query for (int i = 0; i < queries; i++) { int l = Q[i][0], r = Q[i][1]; // Count of odd numbers in l to r int odd = arr_odd[r] - arr_odd[l - 1]; // Count of even numbers in l to r int even = arr_even[r] - arr_even[l - 1]; // Finding the ans int ans = (even * (even - 1) * (even - 2)) / 6 + (odd * (odd - 1) / 2) * even; // Printing the ans cout << ans << " "; }}// Driver Codeint main(){ // Given Input int N = 6, Q = 2; int arr[] = { 1, 2, 3, 4, 5, 6 }; int queries[][2] = { { 1, 3 }, { 2, 5 } }; // Function Call countTriplets(N, Q, arr, queries); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG { // Function to count number of triplets // with even sum in range l, r for each // query static void countTriplets(int size, int queries, int[] arr, int[][] Q) { // Initialization of array int[] arr_even = new int[size + 1]; int []arr_odd = new int[size + 1]; // Initialization of variables int even = 0; int odd = 0; arr_even[0] = 0; arr_odd[0] = 0; // Traversing array for (int i = 0; i < size; i++) { // If element is odd if (arr[i] % 2 == 1) { odd++; } // If element is even else { even++; } // Storing count of even and odd // till each i arr_even[i + 1] = even; arr_odd[i + 1] = odd; } // Traversing each query for (int i = 0; i < queries; i++) { int l = Q[i][0], r = Q[i][1]; // Count of odd numbers in l to r odd = arr_odd[r] - arr_odd[l - 1]; // Count of even numbers in l to r even = arr_even[r] - arr_even[l - 1]; // Finding the ans int ans = (even * (even - 1) * (even - 2)) / 6 + (odd * (odd - 1) / 2) * even; // Printing the ans System.out.print(ans + " "); } } // Driver Code public static void main(String[] args) { // Given Input int N = 6, Q = 2; int[] arr = { 1, 2, 3, 4, 5, 6 }; int[][] queries = { { 1, 3 }, { 2, 5 } }; countTriplets(N, Q, arr, queries); }}// This code is contributed by maddler. |
Python3
# Python 3 program for above approach# Function to count number of triplets# with even sum in range l, r for each# querydef countTriplets(size, queries, arr, Q): # Initialization of array arr_even = [0 for i in range(size + 1)] arr_odd = [0 for i in range(size + 1)] # Initialization of variables even = 0 odd = 0 arr_even[0] = 0 arr_odd[0] = 0 # Traversing array for i in range(size): # If element is odd if (arr[i] % 2): odd += 1 # If element is even else: even += 1 # Storing count of even and odd # till each i arr_even[i + 1] = even arr_odd[i + 1] = odd # Traversing each query for i in range(queries): l = Q[i][0] r = Q[i][1] # Count of odd numbers in l to r odd = arr_odd[r] - arr_odd[l - 1] # Count of even numbers in l to r even = arr_even[r] - arr_even[l - 1] # Finding the ans ans = (even * (even - 1)*(even - 2)) // 6 + (odd * (odd - 1) // 2)* even # Printing the ans print(ans,end = " ")# Driver Codeif __name__ == '__main__': # Given Input N = 6 Q = 2 arr = [1, 2, 3, 4, 5, 6] queries = [[1, 3],[2, 5]] # Function Call countTriplets(N, Q, arr, queries) # This code is contributed by ipg2016107. |
C#
// C# program for above approachusing System;class GFG { // Function to count number of triplets // with even sum in range l, r for each // query static void countTriplets(int size, int queries, int[] arr, int[, ] Q) { // Initialization of array int[] arr_even = new int[size + 1]; int[] arr_odd = new int[size + 1]; // Initialization of variables int even = 0; int odd = 0; arr_even[0] = 0; arr_odd[0] = 0; // Traversing array for (int i = 0; i < size; i++) { // If element is odd if (arr[i] % 2 == 1) { odd++; } // If element is even else { even++; } // Storing count of even and odd // till each i arr_even[i + 1] = even; arr_odd[i + 1] = odd; } // Traversing each query for (int i = 0; i < queries; i++) { int l = Q[i, 0], r = Q[i, 1]; // Count of odd numbers in l to r odd = arr_odd[r] - arr_odd[l - 1]; // Count of even numbers in l to r even = arr_even[r] - arr_even[l - 1]; // Finding the ans int ans = (even * (even - 1) * (even - 2)) / 6 + (odd * (odd - 1) / 2) * even; // Printing the ans Console.Write(ans + " "); } } // Driver Code public static void Main() { // Given Input int N = 6, Q = 2; int[] arr = { 1, 2, 3, 4, 5, 6 }; int[, ] queries = { { 1, 3 }, { 2, 5 } }; countTriplets(N, Q, arr, queries); }}// This code is contributed by subham348. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to count number of triplets // with even sum in range l, r for each // query function countTriplets(size, queries, arr, Q) { // Initialization of array let arr_even = new Array(size + 1); let arr_odd = new Array(size + 1); // Initialization of variables let even = 0; let odd = 0; arr_even[0] = 0; arr_odd[0] = 0; // Traversing array for (let i = 0; i < size; i++) { // If element is odd if (arr[i] % 2 == 1) { odd++; } // If element is even else { even++; } // Storing count of even and odd // till each i arr_even[i + 1] = even; arr_odd[i + 1] = odd; } // Traversing each query for (let i = 0; i < queries; i++) { let l = Q[i][0], r = Q[i][1]; // Count of odd numbers in l to r odd = arr_odd[r] - arr_odd[l - 1]; // Count of even numbers in l to r even = arr_even[r] - arr_even[l - 1]; // Finding the ans let ans = (even * (even - 1) * (even - 2)) / 6 + (odd * (odd - 1) / 2) * even; // Printing the ans document.write(ans + " "); } } // Driver Code // Given Input let N = 6, Q = 2; let arr = [ 1, 2, 3, 4, 5, 6 ]; let queries = [[ 1, 3 ], [ 2, 5 ]]; countTriplets(N, Q, arr, queries);// This code is contributed by sanjoy_62. </script> |
Output:
1 2
Time Complexity: O(N*Q)
Auxiliary Space: O(N)
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!
