Dadas dos secuencias de números enteros ‘A’ y ‘B’, y un número entero ‘k’. La tarea es verificar si podemos igualar ambas secuencias modificando cualquier elemento de la secuencia A de la siguiente manera:
Podemos agregar cualquier número del rango [-k, k] a cualquier elemento de A. Esta operación solo debe realizarse una vez. Escriba Sí si es posible o No en caso contrario.
Ejemplos:
Entrada: K = 2, A[] = {1, 2, 3}, B[] = {3, 2, 1}
Salida: Sí
Se puede agregar 0 a cualquier elemento y ambas secuencias serán iguales.
Entrada: K = 4, A[] = {1, 5}, B[] = {1, 1}
Salida: Sí
-4 se puede sumar a 5, entonces la secuencia A se convierte en {1, 1} que es igual a secuencia b
Enfoque: Tenga en cuenta que para que ambas secuencias sean iguales con un solo movimiento, solo debe haber un elemento que no coincida en ambas secuencias y la diferencia absoluta entre ellos debe ser menor o igual a ‘k’.
- Ordene ambas arrays y busque los elementos que no coinciden.
- Si hay más de un elemento que no coincide, imprima ‘No’
- De lo contrario, encuentre la diferencia absoluta entre los elementos.
- Si la diferencia <= k , imprima ‘Sí’; de lo contrario, imprima ‘No’.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to check if both
// sequences can be made equal
static bool check(int n, int k,
int *a, int *b)
{
// Sorting both the arrays
sort(a,a+n);
sort(b,b+n);
// Flag to tell if there are
// more than one mismatch
bool fl = false;
// To stores the index
// of mismatched element
int ind = -1;
for (int i = 0; i < n; i++)
{
if (a[i] != b[i])
{
// If there is more than one
// mismatch then return False
if (fl == true)
{
return false;
}
fl = true;
ind = i;
}
}
// If there is no mismatch or the
// difference between the
// mismatching elements is <= k
// then return true
if (ind == -1 | abs(a[ind] - b[ind]) <= k)
{
return true;
}
return false;
}
// Driver code
int main()
{
int n = 2, k = 4;
int a[] = {1, 5};
int b[] = {1, 1};
if (check(n, k, a, b))
{
printf("Yes");
}
else
{
printf("No");
}
return 0;
}
// This code is contributed by mits
Java
// Java implementation of the above approach
import java.util.Arrays;
class GFG
{
// Function to check if both
// sequences can be made equal
static boolean check(int n, int k,
int[] a, int[] b)
{
// Sorting both the arrays
Arrays.sort(a);
Arrays.sort(b);
// Flag to tell if there are
// more than one mismatch
boolean fl = false;
// To stores the index
// of mismatched element
int ind = -1;
for (int i = 0; i < n; i++)
{
if (a[i] != b[i])
{
// If there is more than one
// mismatch then return False
if (fl == true)
{
return false;
}
fl = true;
ind = i;
}
}
// If there is no mismatch or the
// difference between the
// mismatching elements is <= k
// then return true
if (ind == -1 | Math.abs(a[ind] - b[ind]) <= k)
{
return true;
}
return false;
}
// Driver code
public static void main(String[] args)
{
int n = 2, k = 4;
int[] a = {1, 5};
int b[] = {1, 1};
if (check(n, k, a, b))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by 29AjayKumar
Python 3
# Python implementation of the above approach
# Function to check if both
# sequences can be made equal
def check(n, k, a, b):
# Sorting both the arrays
a.sort()
b.sort()
# Flag to tell if there are
# more than one mismatch
fl = False
# To stores the index
# of mismatched element
ind = -1
for i in range(n):
if(a[i] != b[i]):
# If there is more than one
# mismatch then return False
if(fl == True):
return False
fl = True
ind = i
# If there is no mismatch or the
# difference between the
# mismatching elements is <= k
# then return true
if(ind == -1 or abs(a[ind]-b[ind]) <= k):
return True
return False
n, k = 2, 4
a =[1, 5]
b =[1, 1]
if(check(n, k, a, b)):
print("Yes")
else:
print("No")
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to check if both
// sequences can be made equal
static bool check(int n, int k,
int[] a, int[] b)
{
// Sorting both the arrays
Array.Sort(a);
Array.Sort(b);
// Flag to tell if there are
// more than one mismatch
bool fl = false;
// To stores the index
// of mismatched element
int ind = -1;
for (int i = 0; i < n; i++)
{
if (a[i] != b[i])
{
// If there is more than one
// mismatch then return False
if (fl == true)
{
return false;
}
fl = true;
ind = i;
}
}
// If there is no mismatch or the
// difference between the
// mismatching elements is <= k
// then return true
if (ind == -1 | Math.Abs(a[ind] - b[ind]) <= k)
{
return true;
}
return false;
}
// Driver code
public static void Main()
{
int n = 2, k = 4;
int[] a = {1, 5};
int[] b = {1, 1};
if (check(n, k, a, b))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Rajput-Ji
PHP
<?php
// PHP implementation of the
// above approach
// Function to check if both
// sequences can be made equal
function check($n, $k, &$a, &$b)
{
// Sorting both the arrays
sort($a);
sort($b);
// Flag to tell if there are
// more than one mismatch
$fl = False;
// To stores the index
// of mismatched element
$ind = -1;
for ($i = 0; $i < $n; $i++)
{
if($a[$i] != $b[$i])
{
// If there is more than one
// mismatch then return False
if($fl == True)
return False;
$fl = True;
$ind = $i;
}
}
// If there is no mismatch or the
// difference between the
// mismatching elements is <= k
// then return true
if($ind == -1 || abs($a[$ind] -
$b[$ind]) <= $k)
return True;
return False;
}
// Driver Code
$n = 2;
$k = 4;
$a = array(1, 5);
$b = array(1, 1);
if(check($n, $k, $a, $b))
echo "Yes";
else
echo "No";
// This code is contributed by ita_c
?>
Javascript
<script>
// Javascript Implementation of above approach.
// Function to check if both
// sequences can be made equal
function check(n, k, a, b)
{
// Sorting both the arrays
a.sort();
b.sort();
// Flag to tell if there are
// more than one mismatch
let fl = false;
// To stores the index
// of mismatched element
let ind = -1;
for (let i = 0; i < n; i++)
{
if (a[i] != b[i])
{
// If there is more than one
// mismatch then return False
if (fl == true)
{
return false;
}
fl = true;
ind = i;
}
}
// If there is no mismatch or the
// difference between the
// mismatching elements is <= k
// then return true
if (ind == -1 | Math.abs(a[ind] - b[ind]) <= k)
{
return true;
}
return false;
}
// Driver code
let n = 2, k = 4;
let a = [1, 5];
let b = [1, 1];
if (check(n, k, a, b))
{
document.write("Yes");
}
else
{
document.write("No");
}
</script>
Producción:
Yes
Complejidad de tiempo: O(nlog(n))
Espacio auxiliar: O(1)