Given an array arr[] consisting of N positive integers, and some queries consisting of a range [L, R], the task is to find whether the sub-array from the given index range can be divided into two contiguous parts of non-zero length and equal sum.
Examples:
Input: arr[] = {1, 1, 2, 3}, q[] = {{0, 1}, {1, 3}, {1, 2}}
Output:
Yes
Yes
No
q[0]: The sub-array can be split into {1}, {1}.
q[1]: The sub-array can be split into {1, 2}, {3}.
q[2]: The sub-array can’t be split into two equal segments.
Input: arr[] = {2, 1, 3, 4, 1, 2}, q[] = {{0, 5}, {1, 3}}
Output:
No
Yes
A simple solution will be to iterate through the entire range and calculate the sum of the range. Then, we will iterate through the entire array again. We will sum up the elements starting from the index ‘L’. If at any step, we find that the current sum is half of the total sum of the range, the sub-array represented by the range can be broken into two equal halves. It can take upto O(n) time to answer a query using this approach.
A better solution is using a prefix-sum array. First, we create a prefix-sum array p_arr of arr. Now, using ‘p_arr’, we can determine the sum of all the elements in the range ‘L’ to ‘R’ in O(1) time. Once, we have our sum, we need to determine if there exists an index ‘i’ from L to R-1 such that the sum of all the numbers between L to i of the original array is half the sum of the range. For, that we can simply insert all the values in the prefix-sum array ‘p_arr’ in an unordered map.
If the value of sum is even and p_arr[l-1] + sum/2 exists in the map, the array can be split into two segments of equal sum.
Thus, the time complexity of answering a query becomes O(1).
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to find the required prefix sum void prefixSum( int * p_arr, int * arr, int n) { p_arr[0] = arr[0]; for ( int i = 1; i < n; i++) p_arr[i] = arr[i] + p_arr[i - 1]; } // Function to hash all the values of prefix // sum array in an unordered map void hashPrefixSum( int * p_arr, int n, unordered_set< int >& q) { for ( int i = 0; i < n; i++) q.insert(p_arr[i]); } // Function to check if a range // can be divided into two equal parts void canDivide( int * p_arr, int n, unordered_set< int >& q, int l, int r) { // To store the value of sum // of entire range int sum; if (l == 0) sum = p_arr[r]; else sum = p_arr[r] - p_arr[l - 1]; // If value of sum is odd if (sum % 2 == 1) { cout << "No" << endl; return ; } // To store p_arr[l-1] int beg = 0; if (l != 0) beg = p_arr[l - 1]; // If the value exists in the map if (q.find(beg + sum / 2) != q.end()) cout << "Yes" << endl; else cout << "No" << endl; } // Driver code int main() { int arr[] = { 1, 1, 2, 3 }; int n = sizeof (arr) / sizeof (arr[0]); // prefix-sum array int p_arr[n]; prefixSum(p_arr, arr, n); // Map to store the values of prefix-sum unordered_set< int > q; hashPrefixSum(p_arr, n, q); // Perform queries canDivide(p_arr, n, q, 0, 1); canDivide(p_arr, n, q, 1, 3); canDivide(p_arr, n, q, 1, 2); return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG { // Function to find the required prefix sum static void prefixSum( int [] p_arr, int [] arr, int n) { p_arr[ 0 ] = arr[ 0 ]; for ( int i = 1 ; i < n; i++) p_arr[i] = arr[i] + p_arr[i - 1 ]; } // Function to q all the values of prefix // sum array in an unordered map static void qPrefixSum( int []p_arr, int n, HashSet<Integer>q) { for ( int i = 0 ; i < n; i++) q.add(p_arr[i]); } // Function to check if a range // can be divided into two equal parts static void canDivide( int [] p_arr, int n, HashSet<Integer>q, int l, int r) { // To store the value of sum // of entire range int sum; if (l == 0 ) sum = p_arr[r]; else sum = p_arr[r] - p_arr[l - 1 ]; // If value of sum is odd if (sum % 2 == 1 ) { System.out.println( "No" ); return ; } // To store p_arr[l-1] int beg = 0 ; if (l != 0 ) beg = p_arr[l - 1 ]; // If the value exists in the map if (q.contains(beg + sum / 2 ) && (beg + sum / 2 )!=( int )q.toArray()[ q.size()- 1 ] ) System.out.println( "Yes" ); else System.out.println( "No" ); } // Driver code public static void main(String[] args) { int arr[] = { 1 , 1 , 2 , 3 }; int n = arr.length; // prefix-sum array int p_arr[] = new int [n]; prefixSum(p_arr, arr, n); // Map to store the values of prefix-sum HashSet<Integer> q = new HashSet<>(); qPrefixSum(p_arr, n, q); // Perform queries canDivide(p_arr, n, q, 0 , 1 ); canDivide(p_arr, n, q, 1 , 3 ); canDivide(p_arr, n, q, 1 , 2 ); } } // This code contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to find the required prefix Sum def prefixSum(p_arr, arr, n): p_arr[ 0 ] = arr[ 0 ] for i in range ( 1 , n): p_arr[i] = arr[i] + p_arr[i - 1 ] # Function to hash all the values of # prefix Sum array in an unordered map def hashPrefixSum(p_arr, n, q): for i in range (n): q[p_arr[i]] = 1 # Function to check if a range # can be divided into two equal parts def canDivide(p_arr, n, q, l, r): # To store the value of Sum # of entire range Sum = 0 if (l = = 0 ): Sum = p_arr[r] else : Sum = p_arr[r] - p_arr[l - 1 ] # If value of Sum is odd if ( Sum % 2 = = 1 ): print ( "No" ) return # To store p_arr[l-1] beg = 0 if (l ! = 0 ): beg = p_arr[l - 1 ] # If the value exists in the map if (beg + Sum / / 2 in q.keys()): print ( "Yes" ) else : print ( "No" ) # Driver code arr = [ 1 , 1 , 2 , 3 ] n = len (arr) # prefix-Sum array p_arr = [ 0 for i in range (n)] prefixSum(p_arr, arr, n) # Map to store the values # of prefix-Sum q = dict () hashPrefixSum(p_arr, n, q) # Perform queries canDivide(p_arr, n, q, 0 , 1 ) canDivide(p_arr, n, q, 1 , 3 ) canDivide(p_arr, n, q, 1 , 2 ) # This code is contributed # by mohit kumar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to find the required prefix sum static void prefixSum( int [] p_arr, int [] arr, int n) { p_arr[0] = arr[0]; for ( int i = 1; i < n; i++) p_arr[i] = arr[i] + p_arr[i - 1]; } // Function to q all the values of prefix // sum array in an unordered map static void qPrefixSum( int []p_arr, int n, HashSet< int >q) { for ( int i = 0; i < n; i++) q.Add(p_arr[i]); } // Function to check if a range // can be divided into two equal parts static void canDivide( int [] p_arr, int n, HashSet< int >q, int l, int r) { // To store the value of sum // of entire range int sum; if (l == 0) sum = p_arr[r]; else sum = p_arr[r] - p_arr[l - 1]; // If value of sum is odd if (sum % 2 == 1) { Console.WriteLine( "No" ); return ; } // To store p_arr[l-1] int beg = 0; if (l != 0) beg = p_arr[l - 1]; // If the value exists in the map if (q.Contains(beg + sum / 2) ) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } // Driver code public static void Main(String[] args) { int []arr = { 1, 1, 2, 3 }; int n = arr.Length; // prefix-sum array int []p_arr = new int [n]; prefixSum(p_arr, arr, n); // Map to store the values of prefix-sum HashSet< int > q = new HashSet< int > (); qPrefixSum(p_arr, n, q); // Perform queries canDivide(p_arr, n, q, 0, 1); canDivide(p_arr, n, q, 1, 3); canDivide(p_arr, n, q, 1, 2); } } // This code has been contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation of the approach // Function to find the required prefix sum function prefixSum(p_arr, arr, n) { p_arr[0] = arr[0]; for ( var i = 1; i < n; i++) p_arr[i] = arr[i] + p_arr[i - 1]; } // Function to hash all the values of prefix // sum array in an unordered map function hashPrefixSum(p_arr, n, q) { for ( var i = 0; i < n; i++) q.add(p_arr[i]); } // Function to check if a range // can be divided into two equal parts function canDivide(p_arr, n, q, l, r) { // To store the value of sum // of entire range var sum; if (l == 0) sum = p_arr[r]; else sum = p_arr[r] - p_arr[l - 1]; // If value of sum is odd if (sum % 2 == 1) { document.write( "No" ); return ; } // To store p_arr[l-1] var beg = 0; if (l != 0) beg = p_arr[l - 1]; // If the value exists in the map if (q.has((beg + sum / 2))) document.write( "Yes<br>" ); else document.write( "No<br>" ); } // Driver code var arr = [1, 1, 2, 3 ]; var n = arr.length; // prefix-sum array var p_arr = Array(n); prefixSum(p_arr, arr, n); // Map to store the values of prefix-sum var q = new Set(); hashPrefixSum(p_arr, n, q); // Perform queries canDivide(p_arr, n, q, 0, 1); canDivide(p_arr, n, q, 1, 3); canDivide(p_arr, n, q, 1, 2); </script> |
Yes Yes No
Auxiliary Space: O(n)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!