Count of all possible Arrays such that each array element can be over the range [1, arr[i]]
Given an array arr[] consisting of N positive integers, the task is to find the number of all possible arrays such that each array element can be over the range [1, arr[i]] all elements in the newly constructed array must be pairwise distinct.
Examples:
Input: arr[] = {5}
Output: 5
Explanation:
All possible arrays that can be formed using the given criteria is {1}, {2}, {3}, {4}, {5}. Therefore, the count of such array is 5.Input: arr[] = {4, 4, 4, 4}
Output: 24
Approach: The given problem can be solved based on the observation that the order of array elements arr[] doesn’t matter which generating the arrays using the new criteria. Below is the illustration for the same:
Illustration:
Consider the array arr[] = {1, 2}, every possible array formed satisfying the given criteria is {1, 2}.
Now, if the order of element of arr[] is changed, say {2, 1}, then every possible array formed satisfying the given criteria is {2, 1}.
Follow the steps below to solve the given problem:
- Sort the array arr[] in non-decreasing order.
- Initialize a variable, say res as 1 that stores the count of all possible arrays formed.
- Traverse the given array arr[] and for each array element arr[i] perform the following steps:
- The count of all possible choices to insert a new array element at index i is arr[i], but to make the array pairwise distinct, all previously selected numbers can’t be selected again. So, the total number of available choices is (arr[i] – i).
- Now, the total number of combinations possible till the index i is given by res*(arr[i] – i). Therefore, update the value of res as res*(arr[i] – i).
- After completing the above steps, print the value of res as the resultant possible count of arrays formed.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find the total number of // arrays of pairwise distinct element // and each element lies in [1, arr[i]] int findArraysInRange( int arr[], int N) { // Stores all possible arrays formed int res = 1; // Sort the array arr[] in the // non-decreasing order sort(arr, arr + N); for ( int i = 0; i < N; i++) { // Total combinations for the // current index i int combinations = (arr[i] - i); // Update the value of res res *= combinations; } // Return the possible count return res; } // Driver Code int main() { int arr[] = { 4, 4, 4, 4 }; int N = sizeof (arr) / sizeof (arr[0]); cout << findArraysInRange(arr, N); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to find the total number of // arrays of pairwise distinct element // and each element lies in [1, arr[i]] static int findArraysInRange( int [] arr, int N) { // Stores all possible arrays formed int res = 1 ; // Sort the array arr[] in the // non-decreasing order Arrays.sort(arr); for ( int i = 0 ; i < N; i++) { // Total combinations for the // current index i int combinations = (arr[i] - i); // Update the value of res res *= combinations; } // Return the possible count return res; } // Driver Code public static void main(String[] args) { int [] arr = { 4 , 4 , 4 , 4 }; int N = arr.length; System.out.print(findArraysInRange(arr, N)); } } // This code is contributed by subhammahato348. |
Python3
# Python program for the above approach # Function to find the total number of # arrays of pairwise distinct element # and each element lies in [1, arr[i]] def findArraysInRange(arr, n): # Sort the array arr.sort() # res Stores all possible arrays formed res = 1 i = 0 # Sort the array arr[] in the # non-decreasing order arr.sort() for i in range ( 0 , n): # Total combinations for the # current index i combinations = (arr[i] - i) # Update the value of res res = res * combinations # Return the possible count return res # Driver Code arr = [ 4 , 4 , 4 , 4 ] N = len (arr) print (findArraysInRange(arr, N)) # This code is contributed by _saurabh_jaiswal |
C#
// C# program for the approach using System; using System.Collections.Generic; class GFG { // Function to find the total number of // arrays of pairwise distinct element // and each element lies in [1, arr[i]] static int findArraysInRange( int [] arr, int N) { // Stores all possible arrays formed int res = 1; // Sort the array arr[] in the // non-decreasing order Array.Sort(arr); for ( int i = 0; i < N; i++) { // Total combinations for the // current index i int combinations = (arr[i] - i); // Update the value of res res *= combinations; } // Return the possible count return res; } // Driver Code public static void Main() { int [] arr = { 4, 4, 4, 4 }; int N = arr.Length; Console.Write(findArraysInRange(arr, N)); } } // This code is contributed by sanjoy_62. |
Javascript
<script> // Javascript program for the above approach // Function to find the total number of // arrays of pairwise distinct element // and each element lies in [1, arr[i]] function findArraysInRange(arr, n, k) { // Sort the array arr.sort((a, b) => a - b); // res Stores all possible arrays formed let res= 1,i=0,combinations; // Sort the array arr[] in the // non-decreasing order arr.sort((a, b) => a - b); for (i = 0; i < N; i++) { // Total combinations for the // current index i combinations = (arr[i] - i); // Update the value of res res = res*combinations; } // Return the possible count return res; } // Driver Code let arr = [4,4,4,4]; let N = arr.length; document.write(findArraysInRange(arr, N)); // This code is contributed by dwivediyash </script> |
24
Time Complexity: O(N*log N)
Auxiliary Space: O(1)