Dada una array de enteros no negativos arr[] . La tarea es encontrar un par (n, r) tal que el valor de n C r sea el máximo posible r < n .
norte C r = norte ! / (r! * (n – r)!)
Ejemplos:
Entrada: arr[] = {5, 2, 3, 4, 1}
Salida: n = 5 y r = 2
5 C 3 = 5! / (3! * (5 – 3)!) = 10
Entrada: arr[] = {0, 2, 3, 4, 1, 6, 8, 9}
Salida: n = 9 y r = 4
Enfoque ingenuo: un enfoque simple es considerar cada par (n, r) y encontrar el valor máximo posible de n C r .
Enfoque eficiente: Se sabe de la combinatoria:
Cuando n es impar:
n C 0 < n C 1 ….. < n C (n-1)/2 = n C (n+1)/2 > ….. > n C n-1 > n C n
Cuando n es par:
n C 0 < n C 1 ….. < n C n/2 > ….. > n C n-1 > n C n
Además, n C r = n C n-r
Se puede observar que n C r será máximo cuando n sea máximo y abs(r – medio) sea mínimo. El problema ahora se reduce a encontrar el elemento más grande en arr[] y r tal que abs(r – medio) sea mínimo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the pair (n, r)
// such that nCr is maximum possible
void findPair(int arr[], int n)
{
// Array should contain atleast 2 elements
if (n < 2) {
cout << "-1";
return;
}
// Maximum element from the array
int maximum = *max_element(arr, arr + n);
// temp stores abs(middle - arr[i])
int temp = 10000001, r = 0, middle = maximum / 2;
// Finding r with minimum abs(middle - arr[i])
for (int i = 0; i < n; i++) {
// When n is even then middle is (maximum / 2)
if (abs(middle - arr[i]) < temp && n % 2 == 0) {
temp = abs(middle - arr[i]);
r = arr[i];
}
// When n is odd then middle elements are
// (maximum / 2) and ((maximum / 2) + 1)
else if (min(abs(middle - arr[i]), abs(middle + 1 - arr[i])) < temp
&& n % 2 == 1) {
temp = min(abs(middle - arr[i]), abs(middle + 1 - arr[i]));
r = arr[i];
}
}
cout << "n = " << maximum
<< " and r = " << r;
}
// Driver code
int main()
{
int arr[] = { 0, 2, 3, 4, 1, 6, 8, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
findPair(arr, n);
return 0;
}
Java
// Java implementation of above approach
class GFG
{
// Function to print the pair (n, r)
// such that nCr is maximum possible
static void findPair(int arr[], int n)
{
// Array should contain atleast 2 elements
if (n < 2)
{
System.out.print("-1");
return;
}
// Maximum element from the array
int maximum = arr[0];
for(int i = 1; i < n; i++)
maximum = Math.max(maximum, arr[i]);
// temp stores abs(middle - arr[i])
int temp = 10000001, r = 0, middle = maximum / 2;
// Finding r with minimum abs(middle - arr[i])
for (int i = 0; i < n; i++)
{
// When n is even then middle is (maximum / 2)
if (Math.abs(middle - arr[i]) < temp && n % 2 == 0)
{
temp = Math.abs(middle - arr[i]);
r = arr[i];
}
// When n is odd then middle elements are
// (maximum / 2) and ((maximum / 2) + 1)
else if (Math.min(Math.abs(middle - arr[i]),
Math.abs(middle + 1 - arr[i])) <
temp && n % 2 == 1)
{
temp = Math.min(Math.abs(middle - arr[i]),
Math.abs(middle + 1 - arr[i]));
r = arr[i];
}
}
System.out.print( "n = " + maximum + " and r = " + r);
}
// Driver code
public static void main(String args[])
{
int arr[] = { 0, 2, 3, 4, 1, 6, 8, 9 };
int n = arr.length;
findPair(arr, n);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
# Function to print the pair (n, r)
# such that nCr is maximum possible
def find_pair(arr):
current_min_diff = float('inf')
n = max(arr)
middle = n / 2
for elem in arr:
diff = abs(elem - middle)
if diff < current_min_diff:
current_min_diff = diff
r = elem
print("n =", n, "and r =", r)
return r
# Driver code
if __name__ == "__main__":
arr = [0, 2, 3, 4, 1, 6, 8, 9]
# arr = [3,2,1.5]
find_pair(arr)
# This code is contributed by AnkitRai01
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the pair (n, r)
// such that nCr is maximum possible
static void findPair(int []arr, int n)
{
// Array should contain atleast 2 elements
if (n < 2)
{
Console.Write("-1");
return;
}
// Maximum element from the array
int maximum = arr[0];
for(int i = 1; i < n; i++)
maximum = Math.Max(maximum, arr[i]);
// temp stores abs(middle - arr[i])
int temp = 10000001, r = 0, middle = maximum / 2;
// Finding r with minimum abs(middle - arr[i])
for (int i = 0; i < n; i++)
{
// When n is even then middle is (maximum / 2)
if (Math.Abs(middle - arr[i]) < temp && n % 2 == 0)
{
temp = Math.Abs(middle - arr[i]);
r = arr[i];
}
// When n is odd then middle elements are
// (maximum / 2) and ((maximum / 2) + 1)
else if (Math.Min(Math.Abs(middle - arr[i]),
Math.Abs(middle + 1 - arr[i])) <
temp && n % 2 == 1)
{
temp = Math.Min(Math.Abs(middle - arr[i]),
Math.Abs(middle + 1 - arr[i]));
r = arr[i];
}
}
Console.Write( "n = " + maximum +
" and r = " + r);
}
// Driver code
public static void Main(String []args)
{
int []arr = { 0, 2, 3, 4, 1, 6, 8, 9 };
int n = arr.Length;
findPair(arr, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Java scriptimplementation of above approach
// Function to print the pair (n, r)
// such that nCr is maximum possible
function findPair(arr,n)
{
// Array should contain atleast 2 elements
if (n < 2)
{
document.write("-1");
return;
}
// Maximum element from the array
let maximum = arr[0];
for(let i = 1; i < n; i++)
maximum = Math.max(maximum, arr[i]);
// temp stores abs(middle - arr[i])
let temp = 10000001, r = 0, middle = maximum / 2;
// Finding r with minimum abs(middle - arr[i])
for (let i = 0; i < n; i++)
{
// When n is even then middle is (maximum / 2)
if (Math.abs(middle - arr[i]) < temp && n % 2 == 0)
{
temp = Math.abs(middle - arr[i]);
r = arr[i];
}
// When n is odd then middle elements are
// (maximum / 2) and ((maximum / 2) + 1)
else if (Math.min(Math.abs(middle - arr[i]),
Math.abs(middle + 1 - arr[i])) <
temp && n % 2 == 1)
{
temp = Math.min(Math.abs(middle - arr[i]),
Math.abs(middle + 1 - arr[i]));
r = arr[i];
}
}
document.write( "n = " + maximum + " and r = " + r);
}
// Driver code
let arr = [0, 2, 3, 4, 1, 6, 8, 9 ];
let n = arr.length;
findPair(arr, n);
// This code is contributed by sravan kumar
</script>
Producción:
n = 9 and r = 4
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AshaRamMeena y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA