Given an integer array having N elements ranging from 1 to N and each element appearing exactly once. The task is to find the number of possible permutations such that the GCD of all elements multiplied with their position is greater than 1.
Note: As the answer can be very large, return the answer modulo 109 + 7
Examples:
Input: N = 2, arr[] = {1, 2}
Output: 1
Explanation: The only valid permutation will be is [2, 1] because GCD(1*2, 2*1) = 2.Input: N = 4, arr[] = {4, 1, 3, 2}
Output: 4
Explanation:
The valid permutations will be
[4, 3, 2, 1] with GCD(1*4, 2*3, 3*2, 4*1) = 2.
[2, 3, 4, 1] with GCD(1*2, 2*3, 3*4, 4*1) = 2.
[2, 1, 4, 3] with GCD(1*2, 2*1, 3*4, 4*3) = 2.
[4, 1, 2, 3] with GCD(1*4, 2*1, 3*2, 4*3) = 2.
Approach: The idea to solve the problem is as follows:
Try to make the product of position and the number even, then in that situation GCD will be at least 2.
So if N is odd then there will 1 more odd element than possible even positions. So no permutation is possible.
Otherwise
- the N/2 even elements can be arranged in (N/2)! ways.
- For each of this arrangement N/2 odd elements can be arranged in (N/2)! ways.
So total number of possible ways are ((N/2)!)2.
Follow the below steps to solve this problem:
- If N is odd then return 0.
- Initialize one variable to store the answer (say ans = 1).
- Traverse from i = 1 to N/2.
- Make ans equal to ans * i * i % MOD.
- Find the mod of ans.
- Return ans.
Below is the implementation of the above approach.
C++
// C++ code to implement the above approach#include <bits/stdc++.h>using namespace std;const int MOD = 1000000007;// Function to find// the number of valid permutationsint ValidPerm(int n, int a[]){ // If n is odd if (n & 1) { return 0; } long long ans = 1; // Counting number of permutations for (int i = 1; i <= n / 2; ++i) { ans *= i * i % MOD; ans %= MOD; } // Return the number of // possible permutations return ans;}// Driver codeint main(){ int N = 4; int arr[N] = { 1, 3, 2, 4 }; // Function call cout << ValidPerm(N, arr); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;public class GFG { static int MOD = 1000000007; // Function to find // the number of valid permutations static int ValidPerm(int n, int a[]) { // If n is odd if ((n & 1) == 1) { return 0; } long ans = 1; // Counting number of permutations for (int i = 1; i <= n / 2; ++i) { ans *= i * i % MOD; ans %= MOD; } // Return the number of // possible permutations return (int)ans; } // Driver code public static void main(String args[]) { int N = 4; int arr[] = { 1, 3, 2, 4 }; // Function call System.out.println(ValidPerm(N, arr)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code to implement the above approachMOD = 1000000007# Function to find# the number of valid permutationsdef ValidPerm(n, a): # If n is odd if (n & 1): return 0 ans = 1 # Counting number of permutations for i in range(1,(n // 2)+1): ans *= i * i % MOD ans %= MOD # Return the number of # possible permutations return ans# Driver codeN = 4arr = [1, 3, 2, 4]# Function callprint(ValidPerm(N, arr));# This code is contributed by shinjanpatra |
C#
// C# code to implement the above approachusing System;public class GFG { static int MOD = 1000000007; // Function to find // the number of valid permutations static int ValidPerm(int n, int []a) { // If n is odd if ((n & 1) == 1) { return 0; } long ans = 1; // Counting number of permutations for (int i = 1; i <= n / 2; ++i) { ans *= i * i % MOD; ans %= MOD; } // Return the number of // possible permutations return (int)ans; } // Driver code public static void Main() { int N = 4; int []arr = { 1, 3, 2, 4 }; // Function call Console.WriteLine(ValidPerm(N, arr)); }}// This code is contributed by jana_sayantan. |
Javascript
<script> // JavaScript code to implement the above approach const MOD = 1000000007; // Function to find // the number of valid permutations const ValidPerm = (n, a) => { // If n is odd if (n & 1) { return 0; } let ans = 1; // Counting number of permutations for (let i = 1; i <= n / 2; ++i) { ans *= i * i % MOD; ans %= MOD; } // Return the number of // possible permutations return ans; } // Driver code let N = 4; let arr = [1, 3, 2, 4]; // Function call document.write(ValidPerm(N, arr));// This code is contributed by rakeshsahni</script> |
4
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
