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 Codeint 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 approachimport 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 Codearr = [4, 4, 4, 4]N = len(arr)print(findArraysInRange(arr, N))Â
# This code is contributed by _saurabh_jaiswal |
C#
// C# program for the approachusing 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 arrayarr.sort((a, b) => a - b);Â
// res Stores all possible arrays formedlet 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> |
Output:Â
24
Â
Time Complexity: O(N*log N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
