Dadas dos arrays arr1[] y arr2[] de tamaño N y M respectivamente, la tarea es contar el número mínimo de intercambios necesarios entre las dos arrays para que la suma de la array arr1 [] sea mayor que la de arr2 [] .
Ejemplos:
Entrada: arr1[] = {1, 3, 2, 4}, arr2[] = {6, 7, 8}
Salida: 1
Explicación:
Intercambiar arr1[0] con arr2[2] hace que la suma de arr1[] sea igual a 17, que es mayor que 14.
Por lo tanto, el número de intercambios necesarios es 1.Entrada: arr1[] = {2, 2}, arr2[] = {5, 5, 5}
Salida: 2
Enfoque: el problema dado se puede resolver clasificando las arrays y realizando los intercambios para maximizar la suma de arr1[] . Siga los pasos a continuación para resolver el problema:
- Ordene ambas arrays y calcule la suma de las arrays como sum1 y sum2 respectivamente.
- Inicialice una cuenta variable como 0 para almacenar la cantidad de intercambios requeridos y j a (M – 1) para apuntar al último elemento de la array arr2[] .
- Recorra el arreglo arr1 [] usando la variable i y realice los siguientes pasos:
- Compruebe si sum1 es menor o igual que sum2 , luego intercambie el elemento actual arr[i] con el elemento arr2[j] para maximizar sum1 .
- Después de intercambiar, actualice el valor de sum1 , sum2 y disminuya j para apuntar al penúltimo elemento e incremente el conteo .
- Después de completar los pasos anteriores, imprima el valor de conteo como el conteo mínimo de intercambios requeridos.
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 minimum count of swaps required
// between the two arrays to make the sum of arr1[] greater
// than that of arr2[]
int maximumCount(int arr1[], int arr2[], int s1, int s2)
{
// Stores the sum of the two arrays
int sum1 = 0, sum2 = 0;
// Calculate sum of arr1[]
for (int i = 0; i < s1; i++)
sum1 += arr1[i];
// Calculate sum of arr2[]
for (int j = 0; j < s2; j++)
sum2 += arr2[j];
int len = 0;
if (s1 >= s2)
len = s2;
else
len = s1;
// Sort the arrays arr1[] and arr2[]
sort(arr1, arr1 + s1);
sort(arr2, arr2 + s2);
int j = 0, k = s2 - 1, count = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++) {
// If the sum1 is less than or equal to sum2
if (sum1 <= sum2) {
// Swapping the elements
if (arr2[k] >= arr1[i]) {
// Update the sum1 and sum2
int dif1 = arr1[j], dif2 = arr2[k];
sum1 -= dif1;
sum1 += dif2;
sum2 -= dif2;
sum2 += dif1;
j++;
k--;
// Increment the count
count++;
}
else
break;
}
else
break;
}
// Return the final count
return count;
}
// Driver Code
int main()
{
int arr1[] = { 1, 3, 2, 4 };
int arr2[] = { 6, 7, 8 };
int N = sizeof(arr1) / sizeof(arr1[0]);
int M = sizeof(arr2) / sizeof(arr2[0]);
// Function Call
cout << maximumCount(arr1, arr2, N, M);
return 0;
}
C
// C program for the above approach
#include <stdio.h>
#include <stdlib.h>
// Compare function for qsort
int cmpfunc(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
// Function to find the minimum count of swaps required
// between the two arrays to make the sum of arr1[] greater
// than that of arr2[]
int maximumCount(int arr1[], int arr2[], int s1, int s2)
{
// Stores the sum of the two arrays
int sum1 = 0, sum2 = 0;
// Calculate sum of arr1[]
for (int i = 0; i < s1; i++)
sum1 += arr1[i];
// Calculate sum of arr2[]
for (int j = 0; j < s2; j++)
sum2 += arr2[j];
int len = 0;
if (s1 >= s2)
len = s2;
else
len = s1;
// Sort the arrays arr1[] and arr2[]
qsort(arr1, s1, sizeof(int), cmpfunc);
qsort(arr2, s2, sizeof(int), cmpfunc);
int j = 0, k = s2 - 1, count = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++) {
// If the sum1 is less than or equal to sum2
if (sum1 <= sum2) {
// Swapping the elements
if (arr2[k] >= arr1[i]) {
// Update the sum1 and sum2
int dif1 = arr1[j], dif2 = arr2[k];
sum1 -= dif1;
sum1 += dif2;
sum2 -= dif2;
sum2 += dif1;
j++;
k--;
// Increment the count
count++;
}
else
break;
}
else
break;
}
// Return the final count
return count;
}
// Driver Code
int main()
{
int arr1[] = { 1, 3, 2, 4 };
int arr2[] = { 6, 7, 8 };
int N = sizeof(arr1) / sizeof(arr1[0]);
int M = sizeof(arr2) / sizeof(arr2[0]);
// Function Call
printf("%d", maximumCount(arr1, arr2, N, M));
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the minimum count
// of swaps required between the two
// arrays to make the sum of arr1[]
// greater than that of arr2[]
static int maximumCount(int[] arr1, int[] arr2, int s1,
int s2)
{
// Stores the sum of the two arrays
int sum1 = 0, sum2 = 0;
// Calculate sum of arr1[]
for (int i = 0; i < s1; i++)
{
sum1 += arr1[i];
}
// Calculate sum of arr2[]
for (int j = 0; j < s2; j++)
{
sum2 += arr2[j];
}
int len = 0;
if (s1 >= s2)
{
len = s2;
}
else
{
len = s1;
}
// Sort the arrays arr1[] and arr2[]
Arrays.sort(arr1);
Arrays.sort(arr2);
int j = 0, k = s2 - 1, count = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++)
{
// If the sum1 is less than
// or equal to sum2
if (sum1 <= sum2)
{
// Swapping the elements
if (arr2[k] >= arr1[i])
{
// Update the sum1 and sum2
int dif1 = arr1[j], dif2 = arr2[k];
sum1 -= dif1;
sum1 += dif2;
sum2 -= dif2;
sum2 += dif1;
j++;
k--;
// Increment the count
count++;
}
else
{
break;
}
}
else
{
break;
}
}
// Return the final count
return count;
}
// Driver Code
public static void main(String[] args)
{
int[] arr1 = new int[] { 1, 3, 2, 4 };
int[] arr2 = new int[] { 6, 7, 8 };
int N = arr1.length;
int M = arr2.length;
// Function Call
System.out.println(maximumCount(arr1, arr2, N, M));
}
}
// This code is contributed by dharanendralv23
Python3
# Python3 program to implement # the above approach # Function to find the minimum count # of swaps required between the two # arrays to make the sum of arr1[] # greater than that of arr2[] def maximumCount(arr1, arr2, s1, s2) : # Stores the sum of the two arrays sum1 = 0 sum2 = 0 # Calculate sum of arr1[] for i in range(s1): sum1 += arr1[i] # Calculate sum of arr2[] for j in range(s2): sum2 += arr2[j] len = 0 if (s1 >= s2) : lenn = s2 else : lenn = s1 # Sort the arrays arr1[] and arr2[] arr1.sort(); arr2.sort(); j = 0 k = s2 - 1 count = 0 # Traverse the array arr[] for i in range(lenn): # If the sum1 is less than # or equal to sum2 if (sum1 <= sum2) : # Swapping the elements if (arr2[k] >= arr1[i]) : # Update the sum1 and sum2 dif1 = arr1[j] dif2 = arr2[k] sum1 -= dif1 sum1 += dif2 sum2 -= dif2 sum2 += dif1 j += 1 k -= 1 # Increment the count count += 1 else : break else : break # Return the final count return count # Driver Code arr1 = [ 1, 3, 2, 4 ] arr2 = [ 6, 7, 8 ] N = len(arr1) M = len(arr2) # Function Call print(maximumCount(arr1, arr2, N, M)) # This code is contributed by sanjoy_62
C#
// C# program for the above approach
using System;
class GFG {
// Function to find the minimum count
// of swaps required between the two
// arrays to make the sum of arr1[]
// greater than that of arr2[]
static int maximumCount(int[] arr1, int[] arr2, int s1,
int s2)
{
// Stores the sum of the two arrays
int sum1 = 0, sum2 = 0;
// Calculate sum of arr1[]
for (int i = 0; i < s1; i++) {
sum1 += arr1[i];
}
// Calculate sum of arr2[]
for (int a = 0; a < s2; a++) {
sum2 += arr2[a];
}
int len = 0;
if (s1 >= s2) {
len = s2;
}
else {
len = s1;
}
// Sort the arrays arr1[] and arr2[]
Array.Sort(arr1);
Array.Sort(arr2);
int j = 0, k = s2 - 1, count = 0;
// Traverse the array arr[]
for (int i = 0; i < len; i++) {
// If the sum1 is less than
// or equal to sum2
if (sum1 <= sum2) {
// Swapping the elements
if (arr2[k] >= arr1[i]) {
// Update the sum1 and sum2
int dif1 = arr1[j], dif2 = arr2[k];
sum1 -= dif1;
sum1 += dif2;
sum2 -= dif2;
sum2 += dif1;
j++;
k--;
// Increment the count
count++;
}
else {
break;
}
}
else {
break;
}
}
// Return the final count
return count;
}
// Driver Code
static public void Main()
{
int[] arr1 = new int[] { 1, 3, 2, 4 };
int[] arr2 = new int[] { 6, 7, 8 };
int N = arr1.Length;
int M = arr2.Length;
// Function Call
Console.WriteLine(maximumCount(arr1, arr2, N, M));
}
}
// This code is contributed by dharanendralv23
Javascript
<script>
// Javascript program of the above approach
// Function to find the minimum count
// of swaps required between the two
// arrays to make the sum of arr1[]
// greater than that of arr2[]
function maximumCount( arr1, arr2, s1,
s2)
{
// Stores the sum of the two arrays
let sum1 = 0, sum2 = 0;
// Calculate sum of arr1[]
for (let i = 0; i < s1; i++)
{
sum1 += arr1[i];
}
// Calculate sum of arr2[]
for (let j = 0; j < s2; j++)
{
sum2 += arr2[j];
}
let len = 0;
if (s1 >= s2)
{
len = s2;
}
else
{
len = s1;
}
// Sort the arrays arr1[] and arr2[]
arr1.sort();
arr2.sort();
let j = 0, k = s2 - 1, count = 0;
// Traverse the array arr[]
for (let i = 0; i < len; i++)
{
// If the sum1 is less than
// or equal to sum2
if (sum1 <= sum2)
{
// Swapping the elements
if (arr2[k] >= arr1[i])
{
// Update the sum1 and sum2
let dif1 = arr1[j], dif2 = arr2[k];
sum1 -= dif1;
sum1 += dif2;
sum2 -= dif2;
sum2 += dif1;
j++;
k--;
// Increment the count
count++;
}
else
{
break;
}
}
else
{
break;
}
}
// Return the final count
return count;
}
// Driver Code
let arr1 = [ 1, 3, 2, 4 ];
let arr2 = [ 6, 7, 8 ];
let N = arr1.length;
let M = arr2.length;
// Function Call
document.write(maximumCount(arr1, arr2, N, M));
</script>
Producción:
1
Complejidad de tiempo: O(N*log N + M*log M)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA