Number of permutations such that pair of indices having odd sum have parity = K
Given an array arr[] of N distinct elements along with an integer K (0 or 1). The task is to find the number of permutations of arr[] such that all possible pairs of indices (i, j) having odd sum ((i + j) must be odd) must follow ((arr[i] + arr[j]) % 2) = K.
Note: The number of permutations can be very large. Therefore, calculate it with mod of (109 + 7).
Examples:
Input: N = 3, K = 1, arr[] = {1, 2, 3}
Output: 2
Explanation: The 2 permutations satisfying the given constraints will be {1, 2, 3} and {3, 2, 1} respectively.
- Permutation {1, 2, 3}: Pair of indices having odd sum are (0, 1) and (1, 2).
- (arr[0] + arr[1]) % 2 = (1 + 2) % 2 = K holds true.
- (arr[1] + arr[2]) % 2 = (2 + 3) % 2= K holds true.
- Permutation {3, 2, 1}: Pair of indices having odd sum are (0, 1) and (1, 2).
- (arr[0] + arr[1]) % 2 = (3 + 2) % 2 = K holds true.
- (arr[1] + arr[2]) % 2 = (2 + 1) % 2 = K holds true.
There are 2 valid permutations satisfying the given constraints. Therefore, output is 2.
Input: N = 5, K = 0, arr[] = {6, 10, 1, 4, 8}
Output: 0
Explanation: It can be verified that there will be no permutation satisfying the given constraints.
Approach: To solve the problem, follow the below idea:
The problem is observation based. There will some cases based on the value K and count of odd and even elements. Let us describe the count of odd and even elements by Odd and Even respectively and a precomputed factorials array as Factorial[]. Now see those cases one by one:
Case 1: (N == 1)
- At base case there can be possible only one permutation as arr[] = {arr[0]}. So, answer for this case is 1.
Case 2: (K == 0 && (Odd == 0 || Even == 0))
- For (K == 0), we can have pairs (arr[i] + arr[j]) with even sum only. As (Sum of two even elements) or (Sum of two odd elements) both gives sum as even. Then, the number of possible permutations for this case will be Factorial[N] as we can arrange elements in any order.
Case 3: (K == 0 || (K == 1 && (Odd == 0 || Even == 0)))
- If after checking case 2 (Just above case), we still have (K == 0), then there must be (Odd != 0) and (Even != 0), we can’t construct valid permutation in such cases. So, the number of possible permutations for this case will be 0.
- Also, if (K == 1). Then we can only have odd sum pairs (i, j) at i = (1, 3, 5. .) and j = (2, 4, 6. .) indices. If we have (Odd == 0 || Even ==0), then it not possible to construct valid permutation of elements as sum will always be even. Therefore, the number of possible permutations for this case will be also 0.
Case 4: Now, we have (K == 1) && (Odd != 0 and Even != 0).
- If (Abs(Odd – Even) > 1), then there will always be at least one pair such that sum will be even so, the valid permutation for such cases will be 0.
- If (Odd – Even) == 1), then, possible permutations = (Factorial[Even]*Factorial[Odd]) (As we can arrange even and odd numbers in any order at i = (1, 3, 5, 7. . .) and j = (2, 4, 6 . .) respectively.
- If (Odd == Even), then arr[]’s length is even. So, we can put odds at (1, 3, 5. .) and evens at (2, 4, 6. .) and vice versa also. Therefore, for such cases the count of valid permutations are = 2*(Factorial[Even]*Factorial[Odd]).
Step-by-step algorithm:
- Declare an array let say Fact[] to hold factorial values and precompute them.
- Create two variables let say Odd and Even to store the count of odd and even elements in arr[].
- Iterate using loops on arr[] and count odd and even elements.
- If (N == 1), Return 1.
- If (K == 0 && (Odd == 0 || Even == 0)), Return Fact[N].
- if (K == 0 || (K == 1 && (Odd == 0 || Even == 0)), return 0.
- Else
- If (Abs(Odd – Even) > 1), return 0.
- Else
- Declare a variable let say Ans.
- If (Odd == Even), Initialize Ans with 2 else 1.
- Ans = ((Ans * Fact[Even]) * Fact[Odd])
- Output Ans.
Below is the implementation of the algorithm:
C++
#include <iostream> using namespace std; // Value of Mod const long long MOD = 1000000007; // Declare len and Fact[] for precomputing factorials // till len const int len = 100001; long long fact[len]; // Function to precompute factorials void PreCompute() { fact[0] = 1; fact[1] = 1; for ( int i = 2; i < len; i++) { fact[i] = (i * fact[i - 1]) % MOD; fact[i] %= MOD; } } // Function to implement the discussed approach void func( int n, int k, int arr[]) { int odd = 0; int eve = 0; // Count the number of odd and even elements in the // array for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 1) odd++; else eve++; } // Base case: If there is only one element in the // array if (n == 1) { cout << "1\n" ; return ; } // Check conditions and calculate result accordingly if (k == 0 && (odd == 0 || eve == 0)) { // If k==0 and either no odd or no even // elements, output factorial of n cout << fact[n] << "\n" ; return ; } if (k == 0 || (k == 1 && (odd == 0 || eve == 0))) { // If k==0 or (k==1 and either no odd or no even // elements), output 0 cout << "0\n" ; } else { if ( abs (odd - eve) > 1) { // If the absolute difference between odd // and even counts > 1, output 0 cout << "0\n" ; } else { // Calculate the answer based on conditions long long ans = (odd == eve) ? 2 : 1; ans = (((ans * fact[eve]) % MOD) * fact[odd]) % MOD; cout << ans << "\n" ; } } } // Driver Function int main() { // Inputs int N = 3; int K = 1; int arr[] = {1, 2, 3}; // Function for Precomputing factorials PreCompute(); // Function call func(N, K, arr); return 0; } // This code is contributed by rambabuguphka |
Java
// Java code to implement the approach import java.util.Scanner; // Driver Class public class Main { // Value of Mod static final long MOD = 1000000007 ; // Declare len and Fact[] for precomputing factorials // till len static int len = 100001 ; static long [] fact = new long [len]; // Driver Function public static void main(String[] args) { // Inputs int N = 3 ; int K = 1 ; int [] arr = { 1 , 2 , 3 }; // Function for Precomputing factorials PreCompute(); // Function call func(N, K, arr); } // Function to precompute factorials public static void PreCompute() { fact[ 0 ] = 1 ; fact[ 1 ] = 1 ; for ( int i = 2 ; i < len; i++) { fact[i] = (i * fact[i - 1 ]) % MOD; fact[i] %= MOD; } } // Function to implement the discussed approach public static void func( int n, int k, int [] arr) { int odd = 0 ; int eve = 0 ; // Count the number of odd and even elements in the // array for ( int i = 0 ; i < n; i++) { if (arr[i] % 2 == 1 ) odd++; else eve++; } // Base case: If there is only one element in the // array if (n == 1 ) { System.out.println(" 1 "); return ; } // Check conditions and calculate result accordingly if (k == 0 && (odd == 0 || eve == 0 )) { // If k==0 and either no odd or no even // elements, output factorial of n System.out.println(fact[n]); return ; } if (k == 0 || (k == 1 && (odd == 0 || eve == 0 ))) { // If k==0 or (k==1 and either no odd or no even // elements), output 0 System.out.println(" 0 "); } else { if (Math.abs(odd - eve) > 1 ) { // If the absolute difference between odd // and even counts > 1, output 0 System.out.println(" 0 "); } else { // Calculate the answer based on conditions long ans = (odd == eve) ? 2 : 1 ; ans = (((ans * fact[eve]) % MOD) * fact[odd]) % MOD; System.out.println(ans); } } } } |
Python3
# Value of Mod MOD = 1000000007 # Declare len and fact[] for precomputing factorials till len len_val = 100001 fact = [ 0 ] * len_val # Function to precompute factorials def pre_compute(): fact[ 0 ] = 1 fact[ 1 ] = 1 for i in range ( 2 , len_val): fact[i] = (i * fact[i - 1 ]) % MOD fact[i] % = MOD # Function to implement the discussed approach def func(n, k, arr): odd = 0 eve = 0 # Count the number of odd and even elements in the array for i in range (n): if arr[i] % 2 = = 1 : odd + = 1 else : eve + = 1 # Base case: If there is only one element in the array if n = = 1 : print ( "1" ) return # Check conditions and calculate result accordingly if k = = 0 and (odd = = 0 or eve = = 0 ): # If k==0 and either no odd or no even elements, output factorial of n print (fact[n]) return if k = = 0 or (k = = 1 and (odd = = 0 or eve = = 0 )): # If k==0 or (k==1 and either no odd or no even elements), output 0 print ( "0" ) else : if abs (odd - eve) > 1 : # If the absolute difference between odd and even counts > 1, output 0 print ( "0" ) else : # Calculate the answer based on conditions ans = 2 if odd = = eve else 1 ans = (((ans * fact[eve]) % MOD) * fact[odd]) % MOD print (ans) # Driver Function if __name__ = = "__main__" : # Inputs N = 3 K = 1 arr = [ 1 , 2 , 3 ] # Function for Precomputing factorials pre_compute() # Function call func(N, K, arr) |
C#
using System; public class Program { // Value of Mod const long MOD = 1000000007; // Declare len and Fact[] for precomputing factorials // till len const int len = 100001; static long [] fact = new long [len]; // Function to precompute factorials static void PreCompute() { fact[0] = 1; fact[1] = 1; for ( int i = 2; i < len; i++) { fact[i] = (i * fact[i - 1]) % MOD; fact[i] %= MOD; } } // Function to implement the discussed approach static void Func( int n, int k, int [] arr) { int odd = 0; int eve = 0; // Count the number of odd and even elements in the // array for ( int i = 0; i < n; i++) { if (arr[i] % 2 == 1) odd++; else eve++; } // Base case: If there is only one element in the // array if (n == 1) { Console.WriteLine( "1" ); return ; } // Check conditions and calculate result accordingly if (k == 0 && (odd == 0 || eve == 0)) { // If k==0 and either no odd or no even // elements, output factorial of n Console.WriteLine(fact[n]); return ; } if (k == 0 || (k == 1 && (odd == 0 || eve == 0))) { // If k==0 or (k==1 and either no odd or no even // elements), output 0 Console.WriteLine( "0" ); } else { if (Math.Abs(odd - eve) > 1) { // If the absolute difference between odd // and even counts > 1, output 0 Console.WriteLine( "0" ); } else { // Calculate the answer based on conditions long ans = (odd == eve) ? 2 : 1; ans = (((ans * fact[eve]) % MOD) * fact[odd]) % MOD; Console.WriteLine(ans); } } } // Driver Function static void Main( string [] args) { // Inputs int N = 3; int K = 1; int [] arr = { 1, 2, 3 }; // Function for Precomputing factorials PreCompute(); // Function call Func(N, K, arr); } } |
Javascript
// Value of Mod const MOD = 1000000007; // Declare len and fact[] for precomputing factorials till len const len = 100001; let fact = new Array(len); // Function to precompute factorials function preCompute() { fact[0] = 1; fact[1] = 1; for (let i = 2; i < len; i++) { fact[i] = (i * fact[i - 1]) % MOD; fact[i] %= MOD; } } // Function to implement the discussed approach function func(n, k, arr) { let odd = 0; let eve = 0; // Count the number of odd and even elements in the array for (let i = 0; i < n; i++) { if (arr[i] % 2 === 1) odd++; else eve++; } // Base case: If there is only one element in the array if (n === 1) { console.log( "1" ); return ; } // Check conditions and calculate result accordingly if (k === 0 && (odd === 0 || eve === 0)) { // If k==0 and either no odd or no even elements, output factorial of n console.log(fact[n]); return ; } if (k === 0 || (k === 1 && (odd === 0 || eve === 0))) { // If k==0 or (k==1 and either no odd or no even elements), output 0 console.log( "0" ); } else { if (Math.abs(odd - eve) > 1) { // If the absolute difference between odd and even counts > 1, output 0 console.log( "0" ); } else { // Calculate the answer based on conditions let ans = (odd === eve) ? 2 : 1; ans = (((ans * fact[eve]) % MOD) * fact[odd]) % MOD; console.log(ans); } } } // Inputs let N = 3; let K = 1; let arr = [1, 2, 3]; // Function for Precomputing factorials preCompute(); // Function call func(N, K, arr); |
2
Time Complexity: O(N), As we are counting odd and even elements and precomputing factorials as well
Auxiliary space: O(100001), As we used array Fact[] of size 100001.