Dadas dos arrays A[] y B[] de igual tamaño, es decir, N que contienen números enteros del 1 al N. La tarea es encontrar sub-arrays de las arrays dadas de modo que tengan la misma suma. Imprima los índices de tales sub-arrays. Si tales subarreglos no son posibles, imprima -1 .
Ejemplos:
Entrada: A[] = {1, 2, 3, 4, 5}, B[] = {6, 2, 1, 5, 4}
Salida:
Índices en el arreglo 1: 0, 1, 2
Índices en el arreglo 2: 0
A[0..2] = 1 + 2 + 3 = 6
B[0] = 6
Entrada: A[] = {10, 1}, B[] = {5, 3}
Salida: -1
No existe tal sub -arrays.
Enfoque: Sea A i la suma de los primeros i elementos de A y B j la suma de los primeros j elementos de B . Sin pérdida de generalidad asumimos que A n <= B n .
Ahora B n >= A n >= A i . Entonces, para cada A i podemos encontrar el j más pequeño tal que A i <= B j . Para cada i encontramos la diferencia
B j – A i .
Si la diferencia es 0, entonces hemos terminado como los elementos del 1 al i enA y 1 a j en B tienen la misma suma. Supongamos que la diferencia no es 0. Entonces la diferencia debe estar en el rango [1, n-1] .
Prueba:
Sea B j – A i >= n
B j >= A i + n
B j-1 >= A i (Como el j-ésimo elemento en B puede ser como mucho n entonces B j <= B j-1 + n )
Ahora bien, esto es una contradicción ya que habíamos asumido que j es el índice más pequeño
tal que B j >= A i es j. Así que nuestra suposición es incorrecta.
Entonces B j – A i < n
Ahora hay n tales diferencias (correspondientes a cada índice) pero solo (n-1) valores posibles, por lo que al menos dos índices producirán la misma diferencia (por el principio de Pigeonhole). Sea A j – B y = A i – B x . Al reorganizar obtenemos A j – A i = B y – B x . Entonces, los subarreglos requeridos son [ i+1, j ] en A y [ x+1, y ] en B .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the valid indices in the array
void printAns(int x, int y, int num)
{
cout << "Indices in array " << num << " : ";
for (int i = x; i < y; ++i) {
cout << i << ", ";
}
cout << y << "\n";
}
// Function to find sub-arrays from two
// different arrays with equal sum
void findSubarray(int N, int a[], int b[], bool swap)
{
// Map to store the indices in A and B
// which produce the given difference
std::map<int, pair<int, int> > index;
int difference;
index[0] = make_pair(-1, -1);
int j = 0;
for (int i = 0; i < N; ++i) {
// Find the smallest j such that b[j] >= a[i]
while (b[j] < a[i]) {
j++;
}
difference = b[j] - a[i];
// Difference encountered for the second time
if (index.find(difference) != index.end()) {
// b[j] - a[i] = b[idx.second] - a[idx.first]
// b[j] - b[idx.second] = a[i] = a[idx.first]
// So sub-arrays are a[idx.first+1...i] and b[idx.second+1...j]
if (swap) {
pair<int, int> idx = index[b[j] - a[i]];
printAns(idx.second + 1, j, 1);
printAns(idx.first + 1, i, 2);
}
else {
pair<int, int> idx = index[b[j] - a[i]];
printAns(idx.first + 1, i, 1);
printAns(idx.second + 1, j, 2);
}
return;
}
// Store the indices for difference in the map
index[difference] = make_pair(i, j);
}
cout << "-1";
}
// Utility function to calculate the
// cumulative sum of the array
void cumulativeSum(int arr[], int n)
{
for (int i = 1; i < n; ++i)
arr[i] += arr[i - 1];
}
// Driver code
int main()
{
int a[] = { 1, 2, 3, 4, 5 };
int b[] = { 6, 2, 1, 5, 4 };
int N = sizeof(a) / sizeof(a[0]);
// Function to update the arrays
// with their cumulative sum
cumulativeSum(a, N);
cumulativeSum(b, N);
if (b[N - 1] > a[N - 1]) {
findSubarray(N, a, b, false);
}
else {
// Swap is true as a and b are swapped during
// function call
findSubarray(N, b, a, true);
}
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
// Function to print the valid indices in the array
static void printAns(int x, int y, int num)
{
System.out.print("Indices in array " + num + " : ");
for (int i = x; i < y; ++i) {
System.out.print(i + ", ");
}
System.out.println(y);
}
// Function to find sub-arrays from two
// different arrays with equal sum
static void findSubarray(int N, int a[], int b[], Boolean swap)
{
// Map to store the indices in A and B
// which produce the given difference
HashMap<Integer,ArrayList<Integer>> index = new HashMap<>();
int difference;
index.put(0 , new ArrayList<Integer>(Arrays.asList(-1, -1)));
int j = 0;
for (int i = 0; i < N; ++i) {
// Find the smallest j such that b[j] >= a[i]
while (b[j] < a[i]) {
j++;
}
difference = b[j] - a[i];
// Difference encountered for the second time
if (index.containsKey(difference)) {
// b[j] - a[i] = b[idx.second] - a[idx.first]
// b[j] - b[idx.second] = a[i] = a[idx.first]
// So sub-arrays are a[idx.first+1...i] and b[idx.second+1...j]
if (swap) {
ArrayList<Integer> idx = index.get(b[j] - a[i]);
printAns(idx.get(1) + 1, j, 1);
printAns(idx.get(0) + 1, i, 2);
}
else {
ArrayList<Integer> idx = index.get(b[j] - a[i]);
printAns(idx.get(0) + 1, i, 1);
printAns(idx.get(1) + 1, j, 2);
}
return;
}
// Store the indices for difference in the map
ArrayList<Integer>arr = new ArrayList<>(Arrays.asList(i,j));
}
System.out.print("-1");
}
// Utility function to calculate the
// cumulative sum of the array
static void cumulativeSum(int arr[], int n)
{
for (int i = 1; i < n; ++i)
arr[i] += arr[i - 1];
}
// Driver code
public static void main(String args[])
{
int a[] = { 1, 2, 3, 4, 5 };
int b[] = { 6, 2, 1, 5, 4 };
int N = a.length;
// Function to update the arrays
// with their cumulative sum
cumulativeSum(a, N);
cumulativeSum(b, N);
if (b[N - 1] > a[N - 1]) {
findSubarray(N, a, b, false);
}
else {
// Swap is true as a and b are swapped during
// function call
findSubarray(N, b, a, true);
}
}
}
// This code is contributed by shinjanpatra
Python3
# Python3 implementation of the approach
# Function to print the valid indices in the array
def printAns(x, y, num):
print("Indices in array", num, ":", end = " ")
for i in range(x, y):
print(i, end = ", ")
print(y)
# Function to find sub-arrays from two
# different arrays with equal sum
def findSubarray(N, a, b, swap):
# Map to store the indices in A and B
# which produce the given difference
index = {}
difference, j = 0, 0
index[0] = (-1, -1)
for i in range(0, N):
# Find the smallest j such that b[j] >= a[i]
while b[j] < a[i]:
j += 1
difference = b[j] - a[i]
# Difference encountered for the second time
if difference in index:
# b[j] - a[i] = b[idx.second] - a[idx.first]
# b[j] - b[idx.second] = a[i] = a[idx.first]
# So sub-arrays are a[idx.first+1...i] and b[idx.second+1...j]
if swap:
idx = index[b[j] - a[i]]
printAns(idx[1] + 1, j, 1)
printAns(idx[0] + 1, i, 2)
else:
idx = index[b[j] - a[i]]
printAns(idx[0] + 1, i, 1)
printAns(idx[1] + 1, j, 2)
return
# Store the indices for difference in the map
index[difference] = (i, j)
print("-1")
# Utility function to calculate the
# cumulative sum of the array
def cumulativeSum(arr, n):
for i in range(1, n):
arr[i] += arr[i - 1]
# Driver code
if __name__ == "__main__":
a = [1, 2, 3, 4, 5]
b = [6, 2, 1, 5, 4]
N = len(a)
# Function to update the arrays
# with their cumulative sum
cumulativeSum(a, N)
cumulativeSum(b, N)
if b[N - 1] > a[N - 1]:
findSubarray(N, a, b, False)
else:
# Swap is true as a and b are
# swapped during function call
findSubarray(N, b, a, True)
# This code is contributed by Rituraj Jain
Javascript
<script>
// JavaScript implementation of the approach
// Function to print the valid indices in the array
function printAns(x, y, num)
{
document.write("Indices in array", num, ":"," ")
for(let i = x; i < y; i++)
document.write(i,", ")
document.write(y,"</br>")
}
// Function to find sub-arrays from two
// different arrays with equal sum
function findSubarray(N, a, b, swap){
// Map to store the indices in A and B
// which produce the given difference
let index = new Map();
let difference = 0, j = 0
index.set(0, [-1, -1])
for(let i = 0; i < N; i++)
{
// Find the smallest j such that b[j] >= a[i]
while(b[j] < a[i])
j += 1
let difference = b[j] - a[i]
// Difference encountered for the second time
if(index.has(difference)){
// b[j] - a[i] = b[idx.second] - a[idx.first]
// b[j] - b[idx.second] = a[i] = a[idx.first]
// So sub-arrays are a[idx.first+1...i] and b[idx.second+1...j]
if(swap){
let idx = index.get(b[j] - a[i])
printAns(idx[1] + 1, j, 1)
printAns(idx[0] + 1, i, 2)
}
else{
let idx = index.get(b[j] - a[i])
printAns(idx[0] + 1, i, 1)
printAns(idx[1] + 1, j, 2)
}
return
// Store the indices for difference in the map
}
index.set(difference,[i, j])
}
document.write("-1")
}
// Utility function to calculate the
// cumulative sum of the array
function cumulativeSum(arr, n){
for(let i = 1; i < n; i++)
arr[i] += arr[i - 1]
}
// Driver code
let a = [1, 2, 3, 4, 5]
let b = [6, 2, 1, 5, 4]
let N = a.length
// Function to update the arrays
// with their cumulative sum
cumulativeSum(a, N)
cumulativeSum(b, N)
if(b[N - 1] > a[N - 1])
findSubarray(N, a, b, false)
else
// Swap is true as a and b are
// swapped during function call
findSubarray(N, b, a, true)
// This code is contributed by shinjanpatra
</script>
Indices in array 1 : 0, 1, 2 Indices in array 2 : 0
Publicación traducida automáticamente
Artículo escrito por HarshSinha1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA