Dadas dos arrays binarias, arr1[] y arr2[] del mismo tamaño n. Encuentre la longitud del tramo común más largo (i, j) donde j >= i tal que arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
La complejidad temporal esperada es Θ(n).
Ejemplos:
C++
// A Simple C++ program to find longest common
// subarray of two binary arrays with same sum
#include<bits/stdc++.h>
using namespace std;
// Returns length of the longest common subarray
// with same sum
int longestCommonSum(bool arr1[], bool arr2[], int n)
{
// Initialize result
int maxLen = 0;
// One by one pick all possible starting points
// of subarrays
for (int i=0; i<n; i++)
{
// Initialize sums of current subarrays
int sum1 = 0, sum2 = 0;
// Consider all points for starting with arr[i]
for (int j=i; j<n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];
// If sums are same and current length is
// more than maxLen, update maxLen
if (sum1 == sum2)
{
int len = j-i+1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
// Driver program to test above function
int main()
{
bool arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
cout << "Length of the longest common span with same "
"sum is "<< longestCommonSum(arr1, arr2, n);
return 0;
}
Java
// A Simple Java program to find longest common
// subarray of two binary arrays with same sum
class Test
{
static int arr1[] = new int[]{0, 1, 0, 1, 1, 1, 1};
static int arr2[] = new int[]{1, 1, 1, 1, 1, 0, 1};
// Returns length of the longest common sum in arr1[]
// and arr2[]. Both are of same size n.
static int longestCommonSum(int n)
{
// Initialize result
int maxLen = 0;
// One by one pick all possible starting points
// of subarrays
for (int i=0; i<n; i++)
{
// Initialize sums of current subarrays
int sum1 = 0, sum2 = 0;
// Consider all points for starting with arr[i]
for (int j=i; j<n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];
// If sums are same and current length is
// more than maxLen, update maxLen
if (sum1 == sum2)
{
int len = j-i+1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.print("Length of the longest common span with same sum is ");
System.out.println(longestCommonSum(arr1.length));
}
}
Python3
# A Simple python program to find longest common
# subarray of two binary arrays with same sum
# Returns length of the longest common subarray
# with same sum
def longestCommonSum(arr1, arr2, n):
# Initialize result
maxLen = 0
# One by one pick all possible starting points
# of subarrays
for i in range(0,n):
# Initialize sums of current subarrays
sum1 = 0
sum2 = 0
# Consider all points for starting with arr[i]
for j in range(i,n):
# Update sums
sum1 += arr1[j]
sum2 += arr2[j]
# If sums are same and current length is
# more than maxLen, update maxLen
if (sum1 == sum2):
len = j-i+1
if (len > maxLen):
maxLen = len
return maxLen
# Driver program to test above function
arr1 = [0, 1, 0, 1, 1, 1, 1]
arr2 = [1, 1, 1, 1, 1, 0, 1]
n = len(arr1)
print("Length of the longest common span with same "
"sum is",longestCommonSum(arr1, arr2, n))
# This code is contributed by
# Smitha Dinesh Semwal
C#
// A Simple C# program to find
// longest common subarray of
// two binary arrays with same sum
using System;
class GFG
{
static int[] arr1 = new int[]{0, 1, 0, 1, 1, 1, 1};
static int[] arr2 = new int[]{1, 1, 1, 1, 1, 0, 1};
// Returns length of the longest
// common sum in arr1[] and arr2[].
// Both are of same size n.
static int longestCommonSum(int n)
{
// Initialize result
int maxLen = 0;
// One by one pick all possible
// starting points of subarrays
for (int i = 0; i < n; i++)
{
// Initialize sums of current
// subarrays
int sum1 = 0, sum2 = 0;
// Consider all points for
// starting with arr[i]
for (int j = i; j < n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];
// If sums are same and current
// length is more than maxLen,
// update maxLen
if (sum1 == sum2)
{
int len = j - i + 1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
// Driver Code
public static void Main()
{
Console.Write("Length of the longest " +
"common span with same sum is ");
Console.Write(longestCommonSum(arr1.Length));
}
}
// This code is contributed
// by ChitraNayal
PHP
<?php
// A Simple PHP program to find
// longest common subarray of
// two binary arrays with same sum
// Returns length of the longest
// common subarray with same sum
function longestCommonSum($arr1, $arr2, $n)
{
// Initialize result
$maxLen = 0;
// One by one pick all possible
// starting points of subarrays
for ($i = 0; $i < $n; $i++)
{
// Initialize sums of
// current subarrays
$sum1 = 0; $sum2 = 0;
// Consider all points
// for starting with arr[i]
for ($j = $i; $j < $n; $j++)
{
// Update sums
$sum1 += $arr1[$j];
$sum2 += $arr2[$j];
// If sums are same and current
// length is more than maxLen,
// update maxLen
if ($sum1 == $sum2)
{
$len = $j - $i + 1;
if ($len > $maxLen)
$maxLen = $len;
}
}
}
return $maxLen;
}
// Driver Code
$arr1 = array(0, 1, 0, 1, 1, 1, 1);
$arr2 = array (1, 1, 1, 1, 1, 0, 1);
$n = sizeof($arr1);
echo "Length of the longest common span ".
"with same ", "sum is ",
longestCommonSum($arr1, $arr2, $n);
// This code is contributed by aj_36
?>
Javascript
<script>
// A Simple Javascript program to find
// longest common subarray of
// two binary arrays with same sum
let arr1 = [0, 1, 0, 1, 1, 1, 1];
let arr2 = [1, 1, 1, 1, 1, 0, 1];
// Returns length of the longest
// common sum in arr1[] and arr2[].
// Both are of same size n.
function longestCommonSum(n)
{
// Initialize result
let maxLen = 0;
// One by one pick all possible
// starting points of subarrays
for (let i = 0; i < n; i++)
{
// Initialize sums of current
// subarrays
let sum1 = 0, sum2 = 0;
// Consider all points for
// starting with arr[i]
for (let j = i; j < n; j++)
{
// Update sums
sum1 += arr1[j];
sum2 += arr2[j];
// If sums are same and current
// length is more than maxLen,
// update maxLen
if (sum1 == sum2)
{
let len = j - i + 1;
if (len > maxLen)
maxLen = len;
}
}
}
return maxLen;
}
document.write("Length of the longest " + "common span with same sum is ");
document.write(longestCommonSum(arr1.length));
</script>
C++
// A O(n) and O(n) extra space C++ program to find
// longest common subarray of two binary arrays with
// same sum
#include<bits/stdc++.h>
using namespace std;
// Returns length of the longest common sum in arr1[]
// and arr2[]. Both are of same size n.
int longestCommonSum(bool arr1[], bool arr2[], int n)
{
// Initialize result
int maxLen = 0;
// Initialize prefix sums of two arrays
int preSum1 = 0, preSum2 = 0;
// Create an array to store starting and ending
// indexes of all possible diff values. diff[i]
// would store starting and ending points for
// difference "i-n"
int diff[2*n+1];
// Initialize all starting and ending values as -1.
memset(diff, -1, sizeof(diff));
// Traverse both arrays
for (int i=0; i<n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];
// Compute current diff and index to be used
// in diff array. Note that diff can be negative
// and can have minimum value as -1.
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;
// If current diff is 0, then there are same number
// of 1's so far in both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0)
maxLen = i+1;
// If current diff is seen first time, then update
// starting index of diff.
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
// Current diff is already seen
else
{
// Find length of this same sum common span
int len = i - diff[diffIndex];
// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
// Driver code
int main()
{
bool arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
cout << "Length of the longest common span with same "
"sum is "<< longestCommonSum(arr1, arr2, n);
return 0;
}
Java
// A O(n) and O(n) extra space Java program to find
// longest common subarray of two binary arrays with
// same sum
class Test
{
static int arr1[] = new int[]{0, 1, 0, 1, 1, 1, 1};
static int arr2[] = new int[]{1, 1, 1, 1, 1, 0, 1};
// Returns length of the longest common sum in arr1[]
// and arr2[]. Both are of same size n.
static int longestCommonSum(int n)
{
// Initialize result
int maxLen = 0;
// Initialize prefix sums of two arrays
int preSum1 = 0, preSum2 = 0;
// Create an array to store starting and ending
// indexes of all possible diff values. diff[i]
// would store starting and ending points for
// difference "i-n"
int diff[] = new int[2*n+1];
// Initialize all starting and ending values as -1.
for (int i = 0; i < diff.length; i++) {
diff[i] = -1;
}
// Traverse both arrays
for (int i=0; i<n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];
// Compute current diff and index to be used
// in diff array. Note that diff can be negative
// and can have minimum value as -1.
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;
// If current diff is 0, then there are same number
// of 1's so far in both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0)
maxLen = i+1;
// If current diff is seen first time, then update
// starting index of diff.
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
// Current diff is already seen
else
{
// Find length of this same sum common span
int len = i - diff[diffIndex];
// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
// Driver method to test the above function
public static void main(String[] args)
{
System.out.print("Length of the longest common span with same sum is ");
System.out.println(longestCommonSum(arr1.length));
}
}
Python
# Python program to find longest common
# subarray of two binary arrays with
# same sum
def longestCommonSum(arr1, arr2, n):
# Initialize result
maxLen = 0
# Initialize prefix sums of two arrays
presum1 = presum2 = 0
# Create a dictionary to store indices
# of all possible sums
diff = {}
# Traverse both arrays
for i in range(n):
# Update prefix sums
presum1 += arr1[i]
presum2 += arr2[i]
# Compute current diff which will be
# used as index in diff dictionary
curr_diff = presum1 - presum2
# If current diff is 0, then there
# are same number of 1's so far in
# both arrays, i.e., (i+1) is
# maximum length.
if curr_diff == 0:
maxLen = i+1
elif curr_diff not in diff:
# save the index for this diff
diff[curr_diff] = i
else:
# calculate the span length
length = i - diff[curr_diff]
maxLen = max(maxLen, length)
return maxLen
# Driver program
arr1 = [0, 1, 0, 1, 1, 1, 1]
arr2 = [1, 1, 1, 1, 1, 0, 1]
print("Length of the longest common",
" span with same", end = " ")
print("sum is",longestCommonSum(arr1,
arr2, len(arr1)))
# This code is contributed by Abhijeet Nautiyal
C#
// A O(n) and O(n) extra space C# program
// to find longest common subarray of two
// binary arrays with same sum
using System;
class GFG
{
static int[] arr1 = new int[]{0, 1, 0, 1, 1, 1, 1};
static int[] arr2 = new int[]{1, 1, 1, 1, 1, 0, 1};
// Returns length of the longest
// common sum in arr1[] and arr2[].
// Both are of same size n.
static int longestCommonSum(int n)
{
// Initialize result
int maxLen = 0;
// Initialize prefix sums of
// two arrays
int preSum1 = 0, preSum2 = 0;
// Create an array to store starting
// and ending indexes of all possible
// diff values. diff[i] would store
// starting and ending points for
// difference "i-n"
int[] diff = new int[2 * n + 1];
// Initialize all starting and ending
// values as -1.
for (int i = 0; i < diff.Length; i++)
{
diff[i] = -1;
}
// Traverse both arrays
for (int i = 0; i < n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];
// Compute current diff and index to
// be used in diff array. Note that
// diff can be negative and can have
// minimum value as -1.
int curr_diff = preSum1 - preSum2;
int diffIndex = n + curr_diff;
// If current diff is 0, then there
// are same number of 1's so far in
// both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0)
maxLen = i + 1;
// If current diff is seen first time,
// then update starting index of diff.
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
// Current diff is already seen
else
{
// Find length of this same
// sum common span
int len = i - diff[diffIndex];
// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
// Driver Code
public static void Main()
{
Console.Write("Length of the longest common " +
"span with same sum is ");
Console.WriteLine(longestCommonSum(arr1.Length));
}
}
// This code is contributed
// by Akanksha Rai(Abby_akku)
Javascript
<script>
// A O(n) and O(n) extra space
// Javascript program to find longest
// common subarray of two binary arrays
// with same sum
let arr1 = [0, 1, 0, 1, 1, 1, 1];
let arr2 = [1, 1, 1, 1, 1, 0, 1];
// Returns length of the longest
// common sum in arr1[] and arr2[].
// Both are of same size n.
function longestCommonSum(n)
{
// Initialize result
let maxLen = 0;
// Initialize prefix sums of
// two arrays
let preSum1 = 0, preSum2 = 0;
// Create an array to store starting
// and ending indexes of all possible
// diff values. diff[i] would store
// starting and ending points for
// difference "i-n"
let diff = new Array(2 * n + 1);
// Initialize all starting and ending
// values as -1.
for (let i = 0; i < diff.length; i++)
{
diff[i] = -1;
}
// Traverse both arrays
for (let i = 0; i < n; i++)
{
// Update prefix sums
preSum1 += arr1[i];
preSum2 += arr2[i];
// Compute current diff and index to
// be used in diff array. Note that
// diff can be negative and can have
// minimum value as -1.
let curr_diff = preSum1 - preSum2;
let diffIndex = n + curr_diff;
// If current diff is 0, then there
// are same number of 1's so far in
// both arrays, i.e., (i+1) is
// maximum length.
if (curr_diff == 0)
maxLen = i + 1;
// If current diff is seen first time,
// then update starting index of diff.
else if ( diff[diffIndex] == -1)
diff[diffIndex] = i;
// Current diff is already seen
else
{
// Find length of this same
// sum common span
let len = i - diff[diffIndex];
// Update max len if needed
if (len > maxLen)
maxLen = len;
}
}
return maxLen;
}
document.write("Length of the longest common "
+ "span with same sum is ");
document.write(longestCommonSum(arr1.length));
</script>
C++
// C++ program to find largest subarray
// with equal number of 0's and 1's.
#include <bits/stdc++.h>
using namespace std;
// Returns largest common subarray with equal
// number of 0s and 1s in both of t
int longestCommonSum(bool arr1[], bool arr2[], int n)
{
// Find difference between the two
int arr[n];
for (int i=0; i<n; i++)
arr[i] = arr1[i] - arr2[i];
// Creates an empty hashMap hM
unordered_map<int, int> hM;
int sum = 0; // Initialize sum of elements
int max_len = 0; // Initialize result
// Traverse through the given array
for (int i = 0; i < n; i++)
{
// Add current element to sum
sum += arr[i];
// To handle sum=0 at last index
if (sum == 0)
max_len = i + 1;
// If this sum is seen before,
// then update max_len if required
if (hM.find(sum) != hM.end())
max_len = max(max_len, i - hM[sum]);
else // Else put this sum in hash table
hM[sum] = i;
}
return max_len;
}
// Driver program to test above function
int main()
{
bool arr1[] = {0, 1, 0, 1, 1, 1, 1};
bool arr2[] = {1, 1, 1, 1, 1, 0, 1};
int n = sizeof(arr1)/sizeof(arr1[0]);
cout << longestCommonSum(arr1, arr2, n);
return 0;
}
Java
// Java program to find largest subarray
// with equal number of 0's and 1's.
import java.io.*;
import java.util.*;
class GFG
{
// Returns largest common subarray with equal
// number of 0s and 1s
static int longestCommonSum(int[] arr1, int[] arr2, int n)
{
// Find difference between the two
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = arr1[i] - arr2[i];
// Creates an empty hashMap hM
HashMap<Integer, Integer> hM = new HashMap<>();
int sum = 0; // Initialize sum of elements
int max_len = 0; // Initialize result
// Traverse through the given array
for (int i = 0; i < n; i++)
{
// Add current element to sum
sum += arr[i];
// To handle sum=0 at last index
if (sum == 0)
max_len = i + 1;
// If this sum is seen before,
// then update max_len if required
if (hM.containsKey(sum))
max_len = Math.max(max_len, i - hM.get(sum));
else // Else put this sum in hash table
hM.put(sum, i);
}
return max_len;
}
// Driver code
public static void main(String args[])
{
int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
int n = arr1.length;
System.out.println(longestCommonSum(arr1, arr2, n));
}
}
// This code is contributed by rachana soma
Python3
# Python program to find largest subarray
# with equal number of 0's and 1's.
# Returns largest common subarray with equal
# number of 0s and 1s
def longestCommonSum(arr1, arr2, n):
# Find difference between the two
arr = [0 for i in range(n)]
for i in range(n):
arr[i] = arr1[i] - arr2[i];
# Creates an empty hashMap hM
hm = {}
sum = 0 # Initialize sum of elements
max_len = 0 #Initialize result
# Traverse through the given array
for i in range(n):
# Add current element to sum
sum += arr[i]
# To handle sum=0 at last index
if (sum == 0):
max_len = i + 1
# If this sum is seen before,
# then update max_len if required
if sum in hm:
max_len = max(max_len, i - hm[sum])
else: # Else put this sum in hash table
hm[sum] = i
return max_len
# Driver code
arr1 = [0, 1, 0, 1, 1, 1, 1]
arr2 = [1, 1, 1, 1, 1, 0, 1]
n = len(arr1)
print(longestCommonSum(arr1, arr2, n))
# This code is contributed by rag2127
C#
// C# program to find largest subarray
// with equal number of 0's and 1's.
using System;
using System.Collections.Generic;
public class GFG
{
// Returns largest common subarray with equal
// number of 0s and 1s
static int longestCommonSum(int[] arr1, int[] arr2, int n)
{
// Find difference between the two
int[] arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = arr1[i] - arr2[i];
// Creates an empty hashMap hM
Dictionary<int,int> hM = new Dictionary<int,int>();
int sum = 0; // Initialize sum of elements
int max_len = 0; // Initialize result
// Traverse through the given array
for (int i = 0; i < n; i++)
{
// Add current element to sum
sum += arr[i];
// To handle sum=0 at last index
if (sum == 0)
max_len = i + 1;
// If this sum is seen before,
// then update max_len if required
if (hM.ContainsKey(sum))
max_len = Math.Max(max_len, i - hM[sum]);
else // Else put this sum in hash table
hM[sum] = i;
}
return max_len;
}
// Driver code
static public void Main ()
{
int[] arr1 = {0, 1, 0, 1, 1, 1, 1};
int[] arr2 = {1, 1, 1, 1, 1, 0, 1};
int n = arr1.Length;
Console.WriteLine(longestCommonSum(arr1, arr2, n));
}
}
// This code is contributed by avanitrachhadiya2155
Javascript
<script>
// Javascript program to find largest subarray
// with equal number of 0's and 1's.
// Returns largest common subarray with equal
// number of 0s and 1s
function longestCommonSum(arr1,arr2,n)
{
// Find difference between the two
let arr = new Array(n);
for (let i = 0; i < n; i++)
arr[i] = arr1[i] - arr2[i];
// Creates an empty hashMap hM
let hM = new Map();
let sum = 0; // Initialize sum of elements
let max_len = 0; // Initialize result
// Traverse through the given array
for (let i = 0; i < n; i++)
{
// Add current element to sum
sum += arr[i];
// To handle sum=0 at last index
if (sum == 0)
max_len = i + 1;
// If this sum is seen before,
// then update max_len if required
if (hM.has(sum))
max_len = Math.max(max_len, i - hM.get(sum));
else // Else put this sum in hash table
hM.set(sum, i);
}
return max_len;
}
// Driver code
let arr1=[0, 1, 0, 1, 1, 1, 1];
let arr2=[1, 1, 1, 1, 1, 0, 1];
let n = arr1.length;
document.write(longestCommonSum(arr1, arr2, n));
// This code is contributed by ab2127
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA