Dada una array arr[] de n enteros positivos. La tarea es encontrar los elementos arr[i] y arr[j] del arreglo tal que arr[i] C arr[j] sea el máximo posible. En caso de más de 1 par válido, imprima cualquiera de ellos.
Ejemplos:
Entrada: arr[] = {3, 1, 2}
Salida: 3 2
3 C 1 = 3
3 C 2 = 3
2 C 1 = 2
(3, 1) y (3, 2) son los únicos pares con n máximo C r .
Entrada: arr[] = {9, 2, 4, 11, 6}
Salida: 11 6
Enfoque: n C r es una función monótona creciente, es decir, n + 1 C r > n C r . Podemos usar este hecho para acercarnos a nuestra respuesta, elegiremos el n máximo entre todos los enteros dados. De esta forma fijamos el valor de n .
Ahora, tenemos que buscar r . Como sabemos que n C r = n C n – r , significa que n C r primero alcanzará su máximo y luego disminuirá.
Si n es impar, entonces nuestro máximo ocurrirá en n / 2y n / 2 + 1 .
Para n = 11 , obtendremos los máximos en 11 C 5 y 11 C 6 .
Cuando n es par, entonces nuestro máximo ocurrirá en n/2 .
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 that gives maximum nCr
void printMaxValPair(vector<long long>& v, int n)
{
sort(v.begin(), v.end());
// This gives the value of N in nCr
long long N = v[n - 1];
// Case 1 : When N is odd
if (N % 2 == 1) {
long long first_maxima = N / 2;
long long second_maxima = first_maxima + 1;
long long ans1 = 3e18, ans2 = 3e18;
long long from_left = -1, from_right = -1;
long long from = -1;
for (long long i = 0; i < n; ++i) {
if (v[i] > first_maxima) {
from = i;
break;
}
else {
long long diff = first_maxima - v[i];
if (diff < ans1) {
ans1 = diff;
from_left = v[i];
}
}
}
from_right = v[from];
long long diff1 = first_maxima - from_left;
long long diff2 = from_right - second_maxima;
if (diff1 < diff2)
cout << N << " " << from_left;
else
cout << N << " " << from_right;
}
// Case 2 : When N is even
else {
long long maxima = N / 2;
long long ans1 = 3e18;
long long R = -1;
for (long long i = 0; i < n - 1; ++i) {
long long diff = abs(v[i] - maxima);
if (diff < ans1) {
ans1 = diff;
R = v[i];
}
}
cout << N << " " << R;
}
}
// Driver code
int main()
{
vector<long long> v = { 1, 1, 2, 3, 6, 1 };
int n = v.size();
printMaxValPair(v, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to print the pair that gives maximum nCr
static void printMaxValPair(Vector<Long> v, int n)
{
Collections.sort(v);
// This gives the value of N in nCr
long N = v.get((int)n - 1);
// Case 1 : When N is odd
if (N % 2 == 1)
{
long first_maxima = N / 2;
long second_maxima = first_maxima + 1;
long ans1 =(long) 3e18, ans2 = (long)3e18;
long from_left = -1, from_right = -1;
long from = -1;
for (long i = 0; i < n; ++i)
{
if (v.get((int)i) > first_maxima)
{
from = i;
break;
}
else
{
long diff = first_maxima - v.get((int)i);
if (diff < ans1)
{
ans1 = diff;
from_left = v.get((int)i);
}
}
}
from_right = v.get((int)from);
long diff1 = first_maxima - from_left;
long diff2 = from_right - second_maxima;
if (diff1 < diff2)
System.out.println( N + " " + from_left);
else
System.out.println( N + " " + from_right);
}
// Case 2 : When N is even
else
{
long maxima = N / 2;
long ans1 =(int) 3e18;
long R = -1;
for (long i = 0; i < n - 1; ++i)
{
long diff = Math.abs(v.get((int)i) - maxima);
if (diff < ans1)
{
ans1 = diff;
R = v.get((int)i);
}
}
System.out.println( N + " " + R);
}
}
// Driver code
public static void main(String args[])
{
long arr[] = { 1, 1, 2, 3, 6, 1};
Vector<Long> v = new Vector<Long>( );
for(int i = 0; i < arr.length; i++)
v.add(arr[i]);
int n = v.size();
printMaxValPair(v, n);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Function to print the pair that # gives maximum nCr def printMaxValPair(v, n): v.sort() # This gives the value of N in nCr N = v[n - 1] # Case 1 : When N is odd if N % 2 == 1: first_maxima = N // 2 second_maxima = first_maxima + 1 ans1, ans2 = 3 * (10 ** 18), 3 * (10 ** 18) from_left, from_right = -1, -1 _from = -1 for i in range(0, n): if v[i] > first_maxima: _from = i break else: diff = first_maxima - v[i] if diff < ans1: ans1 = diff from_left = v[i] from_right = v[_from] diff1 = first_maxima - from_left diff2 = from_right - second_maxima if diff1 < diff2: print(N, from_left) else: print(N, from_right) # Case 2 : When N is even else: maxima = N // 2 ans1 = 3 * (10 ** 18) R = -1 for i in range(0, n - 1): diff = abs(v[i] - maxima) if diff < ans1: ans1 = diff R = v[i] print(N, R) # Driver code if __name__ == "__main__": v = [1, 1, 2, 3, 6, 1] n = len(v) printMaxValPair(v, n) # This code is contributed by # Rituraj Jain
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to print the pair that gives maximum nCr
static void printMaxValPair(List<long> v, int n)
{
v.Sort();
// This gives the value of N in nCr
long N = v[(int)n - 1];
// Case 1 : When N is odd
if (N % 2 == 1)
{
long first_maxima = N / 2;
long second_maxima = first_maxima + 1;
long ans1 = (long) 3e18, ans2 = (long)3e18;
long from_left = -1, from_right = -1;
long from = -1;
for (long i = 0; i < n; ++i)
{
if (v[(int)i] > first_maxima)
{
from = i;
break;
}
else
{
long diff = first_maxima - v[(int)i];
if (diff < ans1)
{
ans1 = diff;
from_left = v[(int)i];
}
}
}
from_right = v[(int)from];
long diff1 = first_maxima - from_left;
long diff2 = from_right - second_maxima;
if (diff1 < diff2)
Console.WriteLine( N + " " + from_left);
else
Console.WriteLine( N + " " + from_right);
}
// Case 2 : When N is even
else
{
long maxima = N / 2;
long ans1 = (long)3e18;
long R = -1;
for (long i = 0; i < n - 1; ++i)
{
long diff = Math.Abs(v[(int)i] - maxima);
if (diff < ans1)
{
ans1 = diff;
R = v[(int)i];
}
}
Console.WriteLine( N + " " + R);
}
}
// Driver code
public static void Main(String []args)
{
long []arr = { 1, 1, 2, 3, 6, 1};
List<long> v = new List<long>( );
for(int i = 0; i < arr.Length; i++)
v.Add(arr[i]);
int n = v.Count;
printMaxValPair(v, n);
}
}
// This code contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the approach
// Function to print the pair that
// gives maximum nCr
function printMaxValPair($v, $n)
{
sort($v);
// This gives the value of N in nCr
$N = $v[$n - 1];
// Case 1 : When N is odd
if ($N % 2 == 1)
{
$first_maxima = $N / 2;
$second_maxima = $first_maxima + 1;
$ans1 = 3e18;
$ans2 = 3e18;
$from_left = -1;
$from_right = -1;
$from = -1;
for ($i = 0; $i < $n; ++$i)
{
if ($v[$i] > $first_maxima)
{
$from = $i;
break;
}
else
{
$diff = $first_maxima - $v[$i];
if ($diff < $ans1)
{
$ans1 = $diff;
$from_left = $v[$i];
}
}
}
$from_right = $v[$from];
$diff1 = $first_maxima - $from_left;
$diff2 = $from_right - $second_maxima;
if ($diff1 < $diff2)
echo $N . " " . $from_left;
else
echo $N . " " . $from_right;
}
// Case 2 : When N is even
else
{
$maxima = $N / 2;
$ans1 = 3e18;
$R = -1;
for ($i = 0; $i < $n - 1; ++$i)
{
$diff = abs($v[$i] - $maxima);
if ($diff < $ans1)
{
$ans1 = $diff;
$R = $v[$i];
}
}
echo $N . " " . $R;
}
}
// Driver code
$v = array( 1, 1, 2, 3, 6, 1 );
$n = count($v);
printMaxValPair($v, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print the pair that gives maximum nCr
function printMaxValPair(v, n)
{
v.sort((a,b)=>a-b)
// This gives the value of N in nCr
var N = v[n - 1];
// Case 1 : When N is odd
if (N % 2 == 1) {
var first_maxima = N / 2;
var second_maxima = first_maxima + 1;
var ans1 = 3000000000000000000, ans2 = 3000000000000000000;
var from_left = -1, from_right = -1;
var from = -1;
for (var i = 0; i < n; ++i) {
if (v[i] > first_maxima) {
from = i;
break;
}
else {
var diff = first_maxima - v[i];
if (diff < ans1) {
ans1 = diff;
from_left = v[i];
}
}
}
from_right = v[from];
var diff1 = first_maxima - from_left;
var diff2 = from_right - second_maxima;
if (diff1 < diff2)
document.write( N + " " + from_left);
else
document.write( N + " " + from_right);
}
// Case 2 : When N is even
else {
var maxima = parseInt(N / 2);
var ans1 = 3000000000000000000;
var R = -1;
for (var i = 0; i < n - 1; ++i) {
var diff = Math.abs(v[i] - maxima);
if (diff < ans1) {
ans1 = diff;
R = v[i];
}
}
document.write( N + " " + R);
}
}
// Driver code
var v = [1, 1, 2, 3, 6, 1 ];
var n = v.length;
printMaxValPair(v, n);
// This code is contributed by famously.
</script>
Producción:
6 3
Complejidad de Tiempo: O(n * log n)
Espacio Auxiliar: O(1)