Given two binary arrays, arr1[] and arr2[] of the same size n. Find the length of the longest common span (i, j) where j >= i such that arr1[i] + arr1[i+1] + …. + arr1[j] = arr2[i] + arr2[i+1] + …. + arr2[j].
The expected time complexity is Θ(n).
Examples:
Input: arr1[] = {0, 1, 0, 0, 0, 0};
arr2[] = {1, 0, 1, 0, 0, 1};
Output: 4
The longest span with same sum is from index 1 to 4.
Input: arr1[] = {0, 1, 0, 1, 1, 1, 1};
arr2[] = {1, 1, 1, 1, 1, 0, 1};
Output: 6
The longest span with same sum is from index 1 to 6.
Input: arr1[] = {0, 0, 0};
arr2[] = {1, 1, 1};
Output: 0
Input: arr1[] = {0, 0, 1, 0};
arr2[] = {1, 1, 1, 1};
Output: 1
We strongly recommend that you click here and practice it, before moving on to the solution.
Method 1 (Simple Solution)
One by one by consider same subarrays of both arrays. For all subarrays, compute sums and if sums are same and current length is more than max length, then update max length. Below is C++ implementation of the simple approach.
Method 1 (Simple Solution)
# 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))
Method 2 (Using Auxiliary Array)
# 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)))
Method 3 (Using Hashing)
# 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))
'Python' 카테고리의 다른 글
[python] Find the minimum distance between two numbers (0) | 2021.09.15 |
---|---|
[python] Union and Intersection of two sorted arrays (0) | 2021.09.15 |