Dadas dos arrays arr1[] y arr2[] que consisten en N enteros positivos y un entero par K , la tarea es verificar si la suma de los mismos elementos indexados en las dos arrays se encuentra en el rango [K/2, K] después de reorganizar las arrays dadas o no. Si es posible obtener dicho acuerdo, escriba «Sí» . De lo contrario, escriba “No” .
Ejemplos:
Entrada: arr1[] = {1, 4, 3, 5}, arr2[] = {0, 2, 1, 1}, K = 6
Salida: Sí
Explicación: Reorganizar arr1[] a {1, 4, 3, 5} y arr2[] a {2, 0, 1, 1} asegura que la suma de los mismos elementos indexados se encuentre en el rango [3, 6]. Por lo tanto, imprima «Sí».Entrada: arr1[] = {2, 0}, arr2[] = {3, 4}, K = 2
Salida: No
Explicación: Tal disposición no es posible
Enfoque ingenuo: el enfoque más simple para generar todas las permutaciones posibles de las arrays dadas y verificar si alguna disposición posible satisface las condiciones dadas o no. Si se encuentra que es cierto, escriba «Sí» . De lo contrario, escriba “No” .
Complejidad de Tiempo: O((N!) 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, siga los pasos a continuación para resolver el problema:
- Ordene la array arr1[] en orden creciente .
- Ordene la array arr2[] en orden decreciente .
- Itere sobre la array y verifique si la suma de los elementos arr1[i] y arr2[i] para todos los valores posibles de i en el rango [0, N – 1] se encuentra en el rango [K/2, K] o no. Si se encuentra que es cierto, escriba «Sí». De lo contrario, escriba “No”.
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 check if there exists any
// arrangements of the arrays such that
// sum of element lie in the range [K/2, K]
void checkArrangement(int A1[], int A2[],
int n, int k)
{
// Sort the array arr1[] in
// increasing order
sort(A1, A1 + n);
// Sort the array arr2[] in
// decreasing order
sort(A2, A2 + n, greater<int>());
int flag = 0;
// Traverse the array
for (int i = 0; i < n; i++) {
// If condition is not satisfied
// break the loop
if ((A1[i] + A2[i] > k)
|| (A1[i] + A2[i] < k / 2)) {
flag = 1;
break;
}
}
// Print the result
if (flag == 1)
cout << "No";
else
cout << "Yes";
}
// Driver Code
int main()
{
int arr1[] = { 1, 3, 4, 5 };
int arr2[] = { 2, 0, 1, 1 };
int K = 6;
int N = sizeof(arr1)
/ sizeof(arr1[0]);
checkArrangement(arr1, arr2, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to check if there exists any
// arrangements of the arrays such that
// sum of element lie in the range [K/2, K]
static void checkArrangement(Integer[] A1,
Integer[] A2,
int n, int k)
{
// Sort the array arr1[] in
// increasing order
Arrays.sort(A1);
// Sort the array arr2[] in
// decreasing order
Arrays.sort(A2, Collections.reverseOrder());
int flag = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If condition is not satisfied
// break the loop
if ((A1[i] + A2[i] > k) ||
(A1[i] + A2[i] < k / 2))
{
flag = 1;
break;
}
}
// Print the result
if (flag == 1)
System.out.println("No");
else
System.out.println("Yes");
}
// Driver Code
public static void main(String[] args)
{
Integer[] arr1 = { 1, 3, 4, 5 };
Integer[] arr2 = { 2, 0, 1, 1 };
int K = 6;
int N = arr1.length;
checkArrangement(arr1, arr2, N, K);
}
}
// This code is contributed by akhilsaini
Python3
# Python3 program for the above approach
# Function to check if there exists any
# arrangements of the arrays such that
# sum of element lie in the range [K/2, K]
def checkArrangement(A1, A2, n, k):
# Sort the array arr1[] in
# increasing order
A1 = sorted(A1)
# Sort the array arr2[] in
# decreasing order
A2 = sorted(A2)
A2 = A2[::-1]
flag = 0
# Traverse the array
for i in range(n):
# If condition is not satisfied
# break the loop
if ((A1[i] + A2[i] > k) or
(A1[i] + A2[i] < k // 2)):
flag = 1
break
# Print the result
if (flag == 1):
print("No")
else:
print("Yes")
# Driver Code
if __name__ == '__main__':
arr1 = [ 1, 3, 4, 5 ]
arr2 = [ 2, 0, 1, 1 ]
K = 6
N = len(arr1)
checkArrangement(arr1, arr2, N, K)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
using System.Collections;
class GFG{
// Function to check if there exists any
// arrangements of the arrays such that
// sum of element lie in the range [K/2, K]
static void checkArrangement(int[] A1, int[] A2,
int n, int k)
{
// Sort the array arr1[] in
// increasing order
Array.Sort(A1);
// Sort the array arr2[] in
// decreasing order
Array.Sort(A2);
Array.Reverse(A2);
int flag = 0;
// Traverse the array
for(int i = 0; i < n; i++)
{
// If condition is not satisfied
// break the loop
if ((A1[i] + A2[i] > k) ||
(A1[i] + A2[i] < k / 2))
{
flag = 1;
break;
}
}
// Print the result
if (flag == 1)
Console.WriteLine("No");
else
Console.WriteLine("Yes");
}
// Driver Code
public static void Main()
{
int[] arr1 = { 1, 3, 4, 5 };
int[] arr2 = { 2, 0, 1, 1 };
int K = 6;
int N = arr1.Length;
checkArrangement(arr1, arr2, N, K);
}
}
// This code is contributed by akhilsaini
Javascript
<script>
// JavaScript program for
// the above approach
// Function to check if there exists any
// arrangements of the arrays such that
// sum of element lie in the range [K/2, K]
function checkArrangement( A1, A2, n, k)
{
// Sort the array arr1[] in
// increasing order
A1.sort();
// Sort the array arr2[] in
// decreasing order
A2.sort();
A2.reverse();
let flag = 0;
// Traverse the array
for(let i = 0; i < n; i++)
{
// If condition is not satisfied
// break the loop
if ((A1[i] + A2[i] > k) ||
(A1[i] + A2[i] < k / 2))
{
flag = 1;
break;
}
}
// Print the result
if (flag == 1)
document.write("No");
else
document.write("Yes");
}
// Driver Code
let arr1 = [ 1, 3, 4, 5 ];
let arr2 = [ 2, 0, 1, 1 ];
let K = 6;
let N = arr1.length;
checkArrangement(arr1, arr2, N, K);
</script>
Yes
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aniket173000 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA