Given an array A[] of N positive integers and 3 integers X, Y, and Z, the task is to check if there exist 4 indices (say p, q, r, s) such that the following conditions are satisfied:
- 0 < p < q < r < s < N
- Sum of the subarray from A[p] to A[q – 1] is X
- Sum of the subarray from A[q] to A[r – 1] is Y
- Sum of the subarray from A[r] to A[s – 1] is Z
Examples:
Input: N = 10, A[] = {1, 3, 2, 2, 2, 3, 1, 4, 3, 2}, X = 5, Y = 7, Z = 5
Output: YES
Explanation: The 4 integers p, q, r, s are {1, 3, 6, 8}.
- A[1] + A[2] = 5
- A[3] + A [4] + A[5] = 7
- A[6] + A[7] = 5
Input: N = 9, A[] = {31, 41, 59, 26, 53, 58, 97, 93, 23}, X = 100, Y = 101, Z = 100
Output: NO
Approach: The problem can be solved easily with the help of cumulative sum and Binary search.
If we calculate the cumulative sum of the array, then the sum of any subarray can be computed in O(1). Say S[i] is cumulative sum till ith index, then S[j] – S[i] = A[i] + A[i + 1] + …. + A[j – 1].
So, given conditions can be converted into the following:
We need to find 4 integers p, q, r, s such that:
S[q] – S[p] = X
S[r] – S[q] = Y
S[s] – S[r] = ZNow, for any fixed index (say p), we can find another index (say q) using binary search in a monotonically increasing array (cumulative sum), such that S[q] = S[p] + X. Similarly, we can find r and s. We can perform this search for all possible indices.
NOTE: A set can be used so that we won’t need to perform a binary search explicitly each time.
Thus, the problem can be solved using the following steps :
- Declare a set (say S).
- Initialize a variable (say curr) by 0, to calculate the cumulative sum at each iteration.
- Iterate through the given array and insert the cumulative sum into the set.
- Iterate through the set and check if the current element of the set satisfies the given condition along with 3 other elements (which are also in the set). If so, return true.
- Else, return false.
Below is the implementation for the above approach:
C++
// C++ code based on the above approach#include <bits/stdc++.h>using namespace std;// Function to check if it is possible to// find 4 integers satisfying the// given conditionbool isPossible(int N, int A[], int X, int Y, int Z){ // Declaring a set set<int> S({ 0 }); // Initializing variable to store // cumulative sum int curr = 0; // Inserting cumulative sums // into the set for (int i = 0; i < N; i++) { curr += A[i]; S.insert(curr); } // Iterating through the set for (auto it : S) { // If current element of set // satisfies the given condition // along with 3 other elements // (which are also in set), // return true if (S.find(it + X) != S.end() && S.find(it + X + Y) != S.end() && S.find(it + X + Y + Z) != S.end()) { return true; } } // Return false if the iteration // completes without getting // the required elements return false;}// Driver codeint main(){ int N = 10, X = 5, Y = 7, Z = 5; int A[] = { 1, 3, 2, 2, 2, 3, 1, 4, 3, 2 }; // Function call int answer = isPossible(N, A, X, Y, Z); if (answer == true) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0;} |
Java
// Java code based on the above approachimport java.util.*;class GFG{ // Function to check if it is possible to // find 4 integers satisfying the // given condition static boolean isPossible(int N, int A[], int X, int Y, int Z) { // Declaring a set HashSet<Integer> S = new HashSet<>(); // Initializing variable to store // cumulative sum int curr = 0; // Inserting cumulative sums // into the set for (int i = 0; i < N; i++) { curr += A[i]; S.add(curr); } // Iterating through the set for (int it : S) { // If current element of set // satisfies the given condition // along with 3 other elements // (which are also in set), // return true if (!S.contains(it + X) && !S.contains(it + X + Y) && !S.contains(it + X + Y + Z) ) { return true; } } // Return false if the iteration // completes without getting // the required elements return false; } // Driver code public static void main(String[] args) { int N = 10, X = 5, Y = 7, Z = 5; int A[] = { 1, 3, 2, 2, 2, 3, 1, 4, 3, 2 }; // Function call boolean answer = isPossible(N, A, X, Y, Z); if (answer == true) { System.out.print("YES" +"\n"); } else { System.out.print("NO" +"\n"); } }}// This code is contributed by shikhasingrajput |
Python3
# Function to check if it is possible to# find 4 integers satisfying the# given conditiondef isPossible(N, A, X, Y, Z) : # Declaring a set S = set() # Initializing variable to store # cumulative sum curr = 0 # Inserting cumulative sums # into the set for i in range(N): curr += A[i] S.add(curr) # Iterating through the set for it in S: # If current element of set # satisfies the given condition # along with 3 other elements # (which are also in set), # return true if ((it + X) in S and (it + X + Y) in S and (it + X + Y + Z) in S) : return True # Return false if the iteration # completes without getting # the required elements return False# Driver codeif __name__ == "__main__": N = 10 X = 5 Y = 7 Z = 5 A = [ 1, 3, 2, 2, 2, 3, 1, 4, 3, 2 ] # Function call answer = isPossible(N, A, X, Y, Z) if (answer == True) : print("YES" ) else : print("NO")# This code is contributed by code_hunt. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{ // Function to check if it is possible to // find 4 integers satisfying the // given condition static bool isPossible(int N, int[] A, int X, int Y, int Z) { // Declaring a set HashSet<int> S = new HashSet<int>(); // Initializing variable to store // cumulative sum int curr = 0; // Inserting cumulative sums // into the set for (int i = 0; i < N; i++) { curr += A[i]; S.Add(curr); } // Iterating through the set foreach (int it in S) { // If current element of set // satisfies the given condition // along with 3 other elements // (which are also in set), // return true if (!S.Contains(it + X) && !S.Contains(it + X + Y) && !S.Contains(it + X + Y + Z) ) { return true; } } // Return false if the iteration // completes without getting // the required elements return false; }static public void Main (){ int N = 10, X = 5, Y = 7, Z = 5; int[] A = { 1, 3, 2, 2, 2, 3, 1, 4, 3, 2 }; // Function call bool answer = isPossible(N, A, X, Y, Z); if (answer == true) { Console.Write("YES" +"\n"); } else { Console.Write("NO" +"\n"); }}}// This code is contributed by sanjoy_62. |
Javascript
// JavaScript code based on the above approach// Function to check if it is possible to// find 4 letters satisfying the// given conditionfunction isPossible(N, A, X, Y, Z) { // Declaring a set let S = new Set([0]); // Initializing variable to store // cumulative sum let curr = 0; // adding cumulative sums // into the set for (let i = 0; i < N; i++) { curr += A[i]; S.add(curr); } // Iterating through the set for (const it of S.values()) { // If current element of set // satisfies the given condition // along with 3 other elements // (which are also in set), // return true if (S.has(it + X) && S.has(it + X + Y) && S.has(it + X + Y + Z)) { return true; } } // Return false if the iteration // completes without getting // the required elements return false;}// Driver codelet N = 10, X = 5, Y = 7, Z = 5;let A = [1, 3, 2, 2, 2, 3, 1, 4, 3, 2];// Function calllet answer = isPossible(N, A, X, Y, Z);if (answer == true) { console.log("YES");} else { console.log("NO");}// This code is contributed by ishankhandelwals. |
Output
YES
Time Complexity: O(N * log(N))
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
