Dados dos arreglos A[] y B[] que consisten en N enteros cada uno y un entero K , la tarea es reorganizar el arreglo B[] de modo que la suma de A i + B i sea como máximo K . Si tal arreglo no es posible, imprima -1 .
Ejemplos:
Entrada: A[] = {1, 2, 3, 4, 2}, B[] = {1, 2, 3, 1, 1}, K = 5
Salida: 1 3 1 1 2Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {2, 3, 4, 5, 6}, K = 6
Salida: -1
Enfoque: La reorganización más óptima de la array B[] para satisfacer las condiciones dadas es ordenar la array en orden descendente .
Prueba:
- Dado que la suma de cada par de i – ésimos elementos indexados puede ser como máximo K. Por lo tanto, mn + num ≤ X y mx + num1 ≤ X , donde mn y mx son los elementos mínimos en el arreglo A[] y B[] respectivamente.
- Por lo tanto, por inducción, se puede probar que mn y mx se pueden aparear.
- Por lo tanto, ordenar la array en orden descendente es la reorganización más óptima.
Siga los pasos a continuación para resolver el problema:
- Ordene la array B[] en orden descendente .
- Recorra la array y verifique si A i + B i es menor o igual que K para cada i -ésimo índice.
- Si la condición falla para cualquier par, imprima -1 .
- De lo contrario, imprima la array B[]
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 rearrange array such
// that sum of similar indexed elements
// does not exceed K
void rearrangeArray(int A[], int B[],
int N, int K)
{
// Sort the array B[]
// in descending order
sort(B, B + N, greater<int>());
bool flag = true;
for (int i = 0; i < N; i++) {
// If condition fails
if (A[i] + B[i] > K) {
flag = false;
break;
}
}
if (!flag) {
cout << "-1" << endl;
}
else {
// Print the array
for (int i = 0; i < N; i++) {
cout << B[i] << " ";
}
}
}
// Driver Code
int main()
{
// Given arrays
int A[] = { 1, 2, 3, 4, 2 };
int B[] = { 1, 2, 3, 1, 1 };
int N = sizeof(A) / sizeof(A[0]);
int K = 5;
rearrangeArray(A, B, N, K);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Reverse array
static int[] reverse(int a[])
{
int i, n = a.length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Function to rearrange array such
// that sum of similar indexed elements
// does not exceed K
static void rearrangeArray(int A[], int B[],
int N, int K)
{
// Sort the array B[]
// in descending order
Arrays.sort(B);
B = reverse(B);
boolean flag = true;
for(int i = 0; i < N; i++)
{
// If condition fails
if (A[i] + B[i] > K)
{
flag = false;
break;
}
}
if (!flag)
{
System.out.print("-1" + "\n");
}
else
{
// Print the array
for(int i = 0; i < N; i++)
{
System.out.print(B[i] + " ");
}
}
}
// Driver Code
public static void main(String[] args)
{
// Given arrays
int A[] = { 1, 2, 3, 4, 2 };
int B[] = { 1, 2, 3, 1, 1 };
int N = A.length;
int K = 5;
rearrangeArray(A, B, N, K);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function to rearrange array such
# that sum of similar indexed elements
# does not exceed K
def rearrangeArray(A, B, N, K):
# Sort the array B[]
# in descending order
B.sort(reverse = True)
flag = True
for i in range(N):
# If condition fails
if (A[i] + B[i] > K):
flag = False
break
if (flag == False):
print("-1")
else:
# Print the array
for i in range(N):
print(B[i], end = " ")
# Driver Code
if __name__ == '__main__':
# Given arrays
A = [ 1, 2, 3, 4, 2 ]
B = [ 1, 2, 3, 1, 1 ]
N = len(A)
K = 5;
rearrangeArray(A, B, N, K)
# This code is contributed by SURENDRA_GANGWAR
C#
// C# program for the
// above approach
using System;
class GFG{
// Reverse array
static int[] reverse(int []a)
{
int i, n = a.Length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Function to rearrange array such
// that sum of similar indexed elements
// does not exceed K
static void rearrangeArray(int []A, int []B,
int N, int K)
{
// Sort the array []B
// in descending order
Array.Sort(B);
B = reverse(B);
bool flag = true;
for(int i = 0; i < N; i++)
{
// If condition fails
if (A[i] + B[i] > K)
{
flag = false;
break;
}
}
if (!flag)
{
Console.Write("-1" + "\n");
}
else
{
// Print the array
for(int i = 0; i < N; i++)
{
Console.Write(B[i] + " ");
}
}
}
// Driver Code
public static void Main(String[] args)
{
// Given arrays
int []A = {1, 2, 3, 4, 2};
int []B = {1, 2, 3, 1, 1};
int N = A.Length;
int K = 5;
rearrangeArray(A, B, N, K);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript program for the above approach
// Reverse array
function reverse(a)
{
let i, n = a.length, t;
for(i = 0; i < n / 2; i++)
{
t = a[i];
a[i] = a[n - i - 1];
a[n - i - 1] = t;
}
return a;
}
// Function to rearrange array such
// that sum of similar indexed elements
// does not exceed K
function rearrangeArray(A, B, N, K)
{
// Sort the array B[]
// in descending order
B.sort();
B = reverse(B);
let flag = true;
for(let i = 0; i < N; i++)
{
// If condition fails
if (A[i] + B[i] > K)
{
flag = false;
break;
}
}
if (!flag)
{
document.write("-1" + "<br/>");
}
else
{
// Print the array
for(let i = 0; i < N; i++)
{
document.write(B[i] + " ");
}
}
}
// Driver Code
// Given arrays
let A = [ 1, 2, 3, 4, 2 ];
let B = [ 1, 2, 3, 1, 1 ];
let N = A.length;
let K = 5;
rearrangeArray(A, B, N, K);
// This code is contribute by target_2
</script>
Producción:
3 2 1 1 1
Complejidad de tiempo: O(N log N), utilizado para ordenar la array dada B
Complejidad de espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por yashrajyash18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA