# Count of triplets in an Array with odd sum

Given an array **arr[] **with **N **integers, find the number of triplets of** i**, **j** and** k** such that **1<= i < j < k <= N** and **arr[i] + arr[j] + arr[k]** is odd.

**Example:**

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.

Input:arr[] = {1, 2, 3, 4, 5}Output:4Explanation:The given array contains 4 triplets with an odd sum. They are {1, 2, 4}, {1, 3, 5}, {2, 3, 4} and {2, 4, 5}.

Input:arr[] ={4, 5, 6, 4, 5, 10, 1, 7}Output:28

**Naive Approach:** The given problem can be solved by iterating over all possible unordered triplets in the array and keep a track of the number of triplets such that their sum is odd.**Time Complexity:** *O(N ^{3})*

**Efficient Approach:** The above approach can be optimized using the below property of integers:

**odd + even + even = odd****odd + odd + odd = odd**

Therefore, to implement the above idea, we can count the number of even and odd integers in the array. Suppose the count of odd integers is **O **and the count of even integers is **E**. So the distinct ways to arrange one odd integer and two even integers is ** ^{O}C_{1 }* ^{E}C_{2 }-> (O * E * (E-1))/2 **and the distinct ways to arrange three odd integers is

**. The final answer will be the sum of the above two values.**

^{O}C_{3 }-> (O * (O-1) * (O-2)) / 6Below is the implementation of the above approach:

## C++

`// C++ Program for the above approach` `#include <iostream>` `using` `namespace` `std;` `// Function to count the number of` `// unordered triplets such that their` `// sum is an odd integer` `int` `countTriplets(` `int` `arr[], ` `int` `n)` `{` ` ` `// Count the number of odd and` ` ` `// even integers in the array` ` ` `int` `odd = 0, even = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++) {` ` ` `if` `(arr[i] & 1)` ` ` `odd++;` ` ` `else` ` ` `even++;` ` ` `}` ` ` `// Number of ways to create triplets` ` ` `// using one odd and two even integers` ` ` `int` `c1 = odd * (even * (even - 1)) / 2;` ` ` `// Number of ways to create triplets` ` ` `// using three odd integers` ` ` `int` `c2 = (odd * (odd - 1) * (odd - 2)) / 6;` ` ` `// Return answer` ` ` `return` `c1 + c2;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `arr[] = { 4, 5, 6, 4, 5, 10, 1, 7 };` ` ` `int` `n = ` `sizeof` `(arr) / ` `sizeof` `(` `int` `);` ` ` `// Function Call` ` ` `int` `ans = countTriplets(arr, n);` ` ` `// Print Answer` ` ` `cout << ans;` ` ` `return` `0;` `}` |

## Java

`// Java program for the above approach` `import` `java.io.*;` `class` `GFG {` `// Function to count the number of` `// unordered triplets such that their` `// sum is an odd integer` `static` `int` `countTriplets(` `int` `arr[], ` `int` `n)` `{` ` ` `// Count the number of odd and` ` ` `// even integers in the array` ` ` `int` `odd = ` `0` `, even = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < n; i++) {` ` ` `if` `((arr[i] & ` `1` `) != ` `0` `)` ` ` `odd++;` ` ` `else` ` ` `even++;` ` ` `}` ` ` `// Number of ways to create triplets` ` ` `// using one odd and two even integers` ` ` `int` `c1 = odd * (even * (even - ` `1` `)) / ` `2` `;` ` ` `// Number of ways to create triplets` ` ` `// using three odd integers` ` ` `int` `c2 = (odd * (odd - ` `1` `) * (odd - ` `2` `)) / ` `6` `;` ` ` `// Return answer` ` ` `return` `c1 + c2;` `}` `// Driver code` `public` `static` `void` `main(String[] args)` `{` ` ` `int` `arr[] = { ` `4` `, ` `5` `, ` `6` `, ` `4` `, ` `5` `, ` `10` `, ` `1` `, ` `7` `};` ` ` `int` `n = arr.length;` ` ` `// Function Call` ` ` `int` `ans = countTriplets(arr, n);` ` ` `// Print Answer` ` ` `System.out.println(ans);` `}` `}` `// This code is contributed by code_hunt.` |

## Python3

`# Python Program for the above approach` `# Function to count the number of` `# unordered triplets such that their` `# sum is an odd integer` `def` `countTriplets(arr, n):` ` ` ` ` `# Count the number of odd and` ` ` `# even integers in the array` ` ` `odd ` `=` `0` ` ` `even ` `=` `0` ` ` `for` `i ` `in` `range` `(n):` ` ` `if` `(arr[i] & ` `1` `):` ` ` `odd` `+` `=` `1` ` ` `else` `:` ` ` `even` `+` `=` `1` ` ` ` ` `# Number of ways to create triplets` ` ` `# using one odd and two even integers` ` ` `c1 ` `=` `odd ` `*` `(even ` `*` `(even ` `-` `1` `)) ` `/` `/` `2` ` ` ` ` `# Number of ways to create triplets` ` ` `# using three odd integers` ` ` `c2 ` `=` `(odd ` `*` `(odd ` `-` `1` `) ` `*` `(odd ` `-` `2` `)) ` `/` `/` `6` ` ` ` ` `# Return answer` ` ` `return` `c1 ` `+` `c2` ` ` ` ` `# Driver Code` `arr ` `=` `[` `4` `, ` `5` `, ` `6` `, ` `4` `, ` `5` `, ` `10` `, ` `1` `, ` `7` `]` `n ` `=` `len` `(arr)` `# Function Call` `ans ` `=` `countTriplets(arr, n)` `# Print Answer` `print` `(ans)` `# This code is contributed by Shivani` |

## C#

`// C# program for the above approach` `using` `System;` `class` `GFG{` `// Function to count the number of unordered` `// triplets such that their sum is an odd integer` `static` `int` `countTriplets(` `int` `[]arr, ` `int` `n)` `{` ` ` ` ` `// Count the number of odd and` ` ` `// even integers in the array` ` ` `int` `odd = 0, even = 0;` ` ` `for` `(` `int` `i = 0; i < n; i++)` ` ` `{` ` ` `if` `((arr[i] & 1) != 0)` ` ` `odd++;` ` ` `else` ` ` `even++;` ` ` `}` ` ` `// Number of ways to create triplets` ` ` `// using one odd and two even integers` ` ` `int` `c1 = odd * (even * (even - 1)) / 2;` ` ` `// Number of ways to create triplets` ` ` `// using three odd integers` ` ` `int` `c2 = (odd * (odd - 1) * (odd - 2)) / 6;` ` ` `// Return answer` ` ` `return` `c1 + c2;` `}` `// Driver code` `public` `static` `void` `Main(String[] args)` `{` ` ` `int` `[]arr = { 4, 5, 6, 4, 5, 10, 1, 7 };` ` ` `int` `n = arr.Length;` ` ` `// Function Call` ` ` `int` `ans = countTriplets(arr, n);` ` ` `// Print Answer` ` ` `Console.Write(ans);` `}` `}` `// This code is contributed by shivanisinghss2110.` |

## Javascript

`<script>` ` ` `// JavaScript program for the above approach;` ` ` `// Function to count the number of` ` ` `// unordered triplets such that their` ` ` `// sum is an odd integer` ` ` `function` `countTriplets(arr, n)` ` ` `{` ` ` ` ` `// Count the number of odd and` ` ` `// even integers in the array` ` ` `let odd = 0, even = 0;` ` ` `for` `(let i = 0; i < n; i++) {` ` ` `if` `(arr[i] & 1)` ` ` `odd++;` ` ` `else` ` ` `even++;` ` ` `}` ` ` `// Number of ways to create triplets` ` ` `// using one odd and two even integers` ` ` `let c1 = Math.floor(odd * (even * (even - 1)) / 2);` ` ` `// Number of ways to create triplets` ` ` `// using three odd integers` ` ` `let c2 = Math.floor((odd * (odd - 1) * (odd - 2)) / 6);` ` ` `// Return answer` ` ` `return` `c1 + c2;` ` ` `}` ` ` `// Driver Code` ` ` `let arr = [4, 5, 6, 4, 5, 10, 1, 7];` ` ` `let n = arr.length;` ` ` `// Function Call` ` ` `let ans = countTriplets(arr, n);` ` ` `// Print Answer` ` ` `document.write(ans);` ` ` `// This code is contributed by Potta Lokesh` ` ` `</script>` |

**Output**

28

**Time Complexity: ***O(N)***Auxiliary Space: ***O(1)*