Number of ways to get even sum by choosing three numbers from 1 to N
Given an integer N, find the number of ways we can choose 3 numbers from {1, 2, 3 …, N} such that their sum is even.
Examples:
Input : N = 3 Output : 1 Explanation: Select 1, 2 and 3 Input : N = 4 Output : 2 Either select (1, 2, 3) or (1, 3, 4)
To get sum even there can be only 2 cases:
- Take 2 odd numbers and 1 even.
- Take all even numbers.
If n is even, Count of odd numbers = n/2 and even = n/2. Else Count odd numbers = n/2 +1 and even = n/2.
Case 1 – No. of ways will be : oddC2 * even.
Case 2 – No. of ways will be : evenC3.
So, total ways will be Case_1_result + Case_2_result.
C++
// C++ program for above implementation #include <bits/stdc++.h> #define MOD 1000000007 using namespace std; // Function to count number of ways int countWays( int N) { long long int count, odd = N / 2, even; if (N & 1) odd = N / 2 + 1; even = N / 2; // Case 1: 2 odds and 1 even count = (((odd * (odd - 1)) / 2) * even) % MOD; // Case 2: 3 evens count = (count + ((even * (even - 1) * (even - 2)) / 6)) % MOD; return count; } // Driver code int main() { int n = 10; cout << countWays(n) << endl; return 0; } |
Java
// java program for above implementation import java.io.*; class GFG { static long MOD = 1000000007 ; // Function to count number of ways static long countWays( int N) { long count, odd = N / 2 , even; if ((N & 1 ) > 0 ) odd = N / 2 + 1 ; even = N / 2 ; // Case 1: 2 odds and 1 even count = (((odd * (odd - 1 )) / 2 ) * even) % MOD; // Case 2: 3 evens count = (count + ((even * (even - 1 ) * (even - 2 )) / 6 )) % MOD; return ( long )count; } // Driver code static public void main (String[] args) { int n = 10 ; System.out.println(countWays(n)); } } // This code is contributed by vt_m. |
Python3
# Python3 code for above implementation MOD = 1000000007 # Function to count number of ways def countWays( N ): odd = N / 2 if N & 1 : odd = N / 2 + 1 even = N / 2 # Case 1: 2 odds and 1 even count = (((odd * (odd - 1 )) / 2 ) * even) % MOD # Case 2: 3 evens count = (count + ((even * (even - 1 ) * (even - 2 )) / 6 )) % MOD return count # Driver code n = 10 print ( int (countWays(n))) # This code is contributed by "Sharad_Bhardwaj" |
C#
// C# program for above implementation using System; public class GFG { static long MOD = 1000000007; // Function to count number of ways static long countWays( int N) { long count, odd = N / 2, even; if ((N & 1) > 0) odd = N / 2 + 1; even = N / 2; // Case 1: 2 odds and 1 even count = (((odd * (odd - 1)) / 2) * even) % MOD; // Case 2: 3 evens count = (count + ((even * (even - 1) * (even - 2)) / 6)) % MOD; return ( long )count; } // Driver code static public void Main () { int n = 10; Console.WriteLine(countWays(n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program for // above implementation $MOD = 1000000007; // Function to count // number of ways function countWays( $N ) { global $MOD ; $count ; $odd = $N / 2; $even ; if ( $N & 1) $odd = $N / 2 + 1; $even = $N / 2; // Case 1: 2 odds // and 1 even $count = ((( $odd * ( $odd - 1)) / 2) * $even ) % $MOD ; // Case 2: 3 evens $count = ( $count + (( $even * ( $even - 1) * ( $even - 2)) / 6)) % $MOD ; return $count ; } // Driver Code $n = 10; echo countWays( $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript program for above implementation let MOD = 1000000007; // Function to count number of ways function countWays(N) { let count, odd = N / 2, even; if ((N & 1) > 0) odd = N / 2 + 1; even = N / 2; // Case 1: 2 odds and 1 even count = (((odd * (odd - 1)) / 2) * even) % MOD; // Case 2: 3 evens count = (count + ((even * (even - 1) * (even - 2)) / 6)) % MOD; return count; } // Driver code let n = 10; document.write(countWays(n)); // This code is contributed by code_hunt. </script> |
Output:
60
Time Complexity: O(1)
Auxiliary Space: O(1)
Contact Us