Dadas dos arrays A[] de longitud N y B[] de longitud N-1 , la tarea es encontrar el entero positivo más pequeño X que se suma a cada elemento de A[] excepto a un elemento, de modo que todos los elementos de la array B[] están presentes en la array A[] . Suponga que encontrar X siempre es posible.
Ejemplos:
Entrada: A[] = {1, 4, 3, 8}, B[] = {15, 8, 11}
Salida: 7
Explicación: Agregar 7 a todos los elementos de la array A excepto 3 dará todos los elementos de la array B
Entrada: A[] = {4, 8}, B[] = {10}
Salida: 2
Explicación : Sumar 2 a 8 da 10.
Enfoque: La idea es utilizar el enfoque codicioso .
- Ordenar las arrays A[] y B[]
- En la observación, se puede ver que el valor de X puede ser B[0] – A[0] o B[0] – A[1] .
- Entonces, A[0] o A[1] no se tienen en cuenta y se agrega X al resto de los elementos.
- Verifique si ambos valores son válidos o no recorriendo la array y si ambos valores X son válidos, elija el mínimo e imprímalo.
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 smallest positive integer
// X such that X is added to every element of A
// except one element to give array B
void findVal(int A[], int B[], int N)
{
// Stores the unique elements of array A
unordered_set<int> s;
for (int i = 0; i < N; i++) {
// Insert A[i] into the set s
s.insert(A[i]);
}
// Sort array A[]
sort(A, A + N);
// Sort array B[]
sort(B, B + N - 1);
// Assume X value as B[0] - A[1]
int X = B[0] - A[1];
// Check if X value assumed is negative or 0
if (X <= 0)
// Update the X value to B[0] - A[0]
X = B[0] - A[0];
else {
for (int i = 0; i < N - 1; i++) {
// If assumed value is wrong
if (s.count(B[i] - X) == 0) {
// Update X value
X = B[0] - A[0];
break;
}
}
}
cout << X << endl;
}
// Driver Code
int main()
{
int A[] = { 1, 4, 3, 8 };
int B[] = { 15, 8, 11 };
int N = sizeof(A) / sizeof(A[0]);
findVal(A, B, N);
return 0;
}
Java
// Java implementation for the above approach
import java.util.*;
public class GFG
{
// Function to find the smallest positive integer
// X such that X is added to every element of A
// except one element to give array B
static void findVal(int []A, int []B, int N)
{
// Stores the unique elements of array A
HashSet<Integer> s = new HashSet<Integer>();
for (int i = 0; i < N; i++) {
// Insert A[i] into the set s
s.add(A[i]);
}
// Sort array A[]
Arrays.sort(A);
// Sort array B[]
Arrays.sort(B);
// Assume X value as B[0] - A[1]
int X = B[0] - A[1];
// Check if X value assumed is negative or 0
if (X <= 0)
// Update the X value to B[0] - A[0]
X = B[0] - A[0];
else {
for (int i = 0; i < N - 1; i++) {
// If assumed value is wrong
if (s.contains(B[i] - X) == false) {
// Update X value
X = B[0] - A[0];
break;
}
}
}
System.out.println(X);
}
// Driver Code
public static void main(String args[])
{
int []A = { 1, 4, 3, 8 };
int []B = { 15, 8, 11 };
int N = A.length;
findVal(A, B, N);
}
}
// This code is contributed by Samim Hossain Mondal
Python3
# Python 3 program for the above approach # Function to find the smallest positive integer # X such that X is added to every element of A # except one element to give array B def findVal(A, B, N): # Stores the unique elements of array A s = set() for i in range(N): # Insert A[i] into the set s s.add(A[i]) # Sort array A[] A.sort() # Sort array B[] B.sort() # Assume X value as B[0] - A[1] X = B[0] - A[1] # Check if X value assumed is negative or 0 if (X <= 0): # Update the X value to B[0] - A[0] X = B[0] - A[0] else: for i in range(N - 1): # If assumed value is wrong if (B[i] - X not in s): # Update X value X = B[0] - A[0] break print(X) # Driver Code if __name__ == '__main__': A = [1, 4, 3, 8] B = [15, 8, 11] N = len(A) findVal(A, B, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to find the smallest positive integer
// X such that X is added to every element of A
// except one element to give array B
static void findVal(int []A, int []B, int N)
{
// Stores the unique elements of array A
HashSet<int> s = new HashSet<int>();
for (int i = 0; i < N; i++) {
// Insert A[i] into the set s
s.Add(A[i]);
}
// Sort array A[]
Array.Sort(A);
// Sort array B[]
Array.Sort(B);
// Assume X value as B[0] - A[1]
int X = B[0] - A[1];
// Check if X value assumed is negative or 0
if (X <= 0)
// Update the X value to B[0] - A[0]
X = B[0] - A[0];
else {
for (int i = 0; i < N - 1; i++) {
// If assumed value is wrong
if (s.Contains(B[i] - X) == false) {
// Update X value
X = B[0] - A[0];
break;
}
}
}
Console.Write(X);
}
// Driver Code
public static void Main()
{
int []A = { 1, 4, 3, 8 };
int []B = { 15, 8, 11 };
int N = A.Length;
findVal(A, B, N);
}
}
// This code is contributed by Samim Hossain Mondal
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the smallest positive integer
// X such that X is added to every element of A
// except one element to give array B
function findVal(A, B, N)
{
// Stores the unique elements of array A
let s = new Set();
for (let i = 0; i < N; i++)
{
// Insert A[i] into the set s
s.add(A[i]);
}
// Sort array A[]
A.sort(function (a, b) { return a - b });
// Sort array B[]
B.sort(function (a, b) { return a - b })
// Assume X value as B[0] - A[1]
let X = B[0] - A[1];
// Check if X value assumed is negative or 0
if (X <= 0)
// Update the X value to B[0] - A[0]
X = B[0] - A[0];
else {
for (let i = 0; i < N - 1; i++) {
// If assumed value is wrong
if (s.has(B[i] - X) == false) {
// Update X value
X = B[0] - A[0];
break;
}
}
}
document.write(X);
}
// Driver Code
let A = [1, 4, 3, 8];
let B = [15, 8, 11];
let N = A.length;
findVal(A, B, N);
// This code is contributed by Potta Lokesh
</script>
Producción
7
Complejidad temporal: O(N log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por dharanendralv23 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA