Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar el número de todas las arrays posibles de modo que cada elemento de la array pueda estar sobre el rango [1, arr[i]] todos los elementos de la array recién construida deben estar por pares distintos .
Ejemplos:
Entrada: arr[] = {5}
Salida: 5
Explicación:
Todas las arrays posibles que se pueden formar usando los criterios dados son {1}, {2}, {3}, {4}, {5}. Por lo tanto, el conteo de dicha array es 5.Entrada: arr[] = {4, 4, 4, 4}
Salida: 24
Enfoque: el problema dado se puede resolver basándose en la observación de que el orden de los elementos de la array arr[] no importa cuál genere las arrays utilizando los nuevos criterios. A continuación se muestra la ilustración de la misma:
Ilustración:
Considere la array arr[] = {1, 2}, cada array posible formada que satisfaga los criterios dados es {1, 2}.
Ahora, si se cambia el orden de los elementos de arr[], digamos {2, 1}, entonces cada arreglo posible formado que satisfaga los criterios dados es {2, 1}.
Siga los pasos a continuación para resolver el problema dado:
- Ordene la array arr[] en orden no decreciente .
- Inicialice una variable, digamos res como 1 que almacene el recuento de todas las arrays posibles formadas.
- Recorra la array dada arr[] y para cada elemento de la array arr[i] realice los siguientes pasos:
- El recuento de todas las opciones posibles para insertar un nuevo elemento de array en el índice i es arr[i] , pero para que la array se distinga por pares, todos los números seleccionados previamente no se pueden seleccionar nuevamente. Entonces, el número total de opciones disponibles es (arr[i] – i) .
- Ahora, el número total de combinaciones posibles hasta el índice i viene dado por res*(arr[i] – i) . Por lo tanto, actualice el valor de res como res*(arr[i] – i) .
- Después de completar los pasos anteriores, imprima el valor de res como el posible recuento resultante de arrays formadas.
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA