Given an array X[] of size N, then the task is to output the number of sub-arrays satisfying the given condition: The Sum of (X[i] – X[i+1]) in any sub-array from L to R(1<= L, R <= N) is not equal to X[R] – X[L].
Examples:
Input: N = 3, X[] = {20, 40, 60}
Output: 3
Explanation: There are three sub-arrays satisfying the given condition:
- X[1, 2] = (20 – 40) = -20, Which is not equal to (40 – 20) = 20.
- X[2, 3] = (40 – 60) = -20, Which is not equal to (60 – 40) = 20.
- X[1, 3] = (20 – 40) + (40 – 60) = -40, Which is not equal to (60 – 40) = 40. Hence, there are 3 sub-arrays.
Input: N = 5, X[] = {3, 4, 4, 5, 1}
Output: 9
Explanation: It can be verified that there are 9 sub-arrays satisfying the given conditions.
Approach: Implement the idea below to solve the problem
The problem is observation based and can be solved by using the HashMap data structure. For more clarification, see the Concept of Approach section below.
Concept of Approach:
- In this problem, one thing is to observe that if a subarray begins and ends with the same number, it won’t be considered an unstable subarray.
- So if the frequency of an element is greater than 1, and its frequency is F(say), so the number of non-unstable arrays contributed by that element is F*(F-1)/2.
- Calculate all possible non-unstable subarrays and subtract them from all possible subarrays.
Steps were taken to solve the problem:
- Create a HashMap let’s say Map.
- Traverse X[] and initialize the frequency of elements in the map.
- Create variable totalPairs and initialize it with N*(N-1)/2.
- Traverse the map using the loop and follow the below-mentioned steps under the scope of the loop:
- Create variable freq and initialize it with the frequency of the current element.
- Update freq as freq*(freq-1)/2.
- Subtract the value of freq from totalPairs. Formally, totalPairs-=freq.
- Return the value of totalPairs.
Below is the code to implement the approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Method for calculating number of // Sub-ararys long long Max_SubArrays( int N, int X[]) { // HashMap for storing frequencies // of elements unordered_map< int , int > map; // Loop for initializing frequency // in map for ( int i = 0; i < N; i++) { map[X[i]]++; } // total number of pairs long long totalPair = N * (N - 1) / 2; // Loop for traversing map for ( auto it = map.begin(); it != map.end(); it++) { // Getting frequency of current // element long long freq = it->second; // Pairs due to frequency of // current element long long pairwithNum = freq * (freq - 1) / 2; // Subtracting pairs from total // number of sub-arrays totalPair -= pairwithNum; } // Returning ans return (totalPair); } // Driver Function int main() { // Inputs int N = 5; int X[] = { 3, 4, 4, 5, 1 }; // Function call for printing ans cout << Max_SubArrays(N, X); return 0; } // This code is contributed by Tapesh(tapeshdua420) |
Java
// Java code to implement the approach import java.util.*; public class GFG { // Driver Function public static void main(String[] args) { // Inputs int N = 5 ; int X[] = { 3 , 4 , 4 , 5 , 1 }; // Function call for printing ans System.out.println(Max_SubArrays(N, X)); } // Method for calculating number of // Sub-ararys public static long Max_SubArrays( int N, int [] X) { // HashMap for storing frequencies // of elements HashMap<Integer, Integer> map = new HashMap<>(); // Loop for initializing frequency // in map for ( int i = 0 ; i < N; i++) { map.put(X[i], map.getOrDefault(X[i], 0 ) + 1 ); } // total number of pairs long totalPair = N * (N - 1 ) / 2 ; // Loop for traversing map for (Map.Entry<Integer, Integer> entry : map.entrySet()) { // Getting frequency of current // element long freq = entry.getValue(); // Pairs due to frequency of // current element long pairwithNum = freq * (freq - 1 ) / 2 ; // Subtracting pairs from total // number of sub-arrays totalPair -= pairwithNum; } // Returning ans return (totalPair); } } |
Python3
# Python code to implement the approach # Method for calculating number of # Sub-ararys def Max_SubArrays(N, X): # Dictionary for storing frequencies of elements map = {} # Loop for initializing frequency in the map for i in range (N): map [X[i]] = map .get(X[i], 0 ) + 1 # Total number of pairs total_pair = N * (N - 1 ) / / 2 # Loop for traversing the map for freq in map .values(): # Pairs due to frequency of the current element pair_with_num = freq * (freq - 1 ) / / 2 # Subtracting pairs from the total number of sub-arrays total_pair - = pair_with_num # Returning the answer return total_pair # Driver Function def main(): # Inputs N = 5 X = [ 3 , 4 , 4 , 5 , 1 ] # Function call for printing the answer print (Max_SubArrays(N, X)) if __name__ = = "__main__" : main() # This code is contributed by Vaibhav Nandan |
C#
// C# code to implement the approach using System; using System.Collections.Generic; class GFG { // Driver Function static void Main( string [] args) { // Inputs int N = 5; int [] X = { 3, 4, 4, 5, 1 }; // Function call for printing ans Console.WriteLine(Max_SubArrays(N, X)); } // Method for calculating number of Sub-arrays static long Max_SubArrays( int N, int [] X) { // Dictionary for storing frequencies of elements Dictionary< int , int > map = new Dictionary< int , int >(); // Loop for initializing frequency in map for ( int i = 0; i < N; i++) { if (map.ContainsKey(X[i])) map[X[i]]++; else map[X[i]] = 1; } // total number of pairs long totalPair = N * (N - 1) / 2; // Loop for traversing map foreach (KeyValuePair< int , int > entry in map) { // Getting frequency of current element long freq = entry.Value; // Pairs due to frequency of current element long pairwithNum = freq * (freq - 1) / 2; // Subtracting pairs from total number of sub-arrays totalPair -= pairwithNum; } // Returning ans return totalPair; } } // This code is contributed by Pushpesh Raj |
Javascript
//Javascript code // Function for calculating number of // Sub-ararys function maxSubArrays(N, X) { const map = new Map(); for (let i = 0; i < N; i++) { if (map.has(X[i])) { map.set(X[i], map.get(X[i]) + 1); } else { map.set(X[i], 1); } } let totalPair = (N * (N - 1)) / 2; // Loop for traversing map for (const [num, freq] of map) { const pairWithNum = (freq * (freq - 1)) / 2; // Subtracting pairs from total // number of sub-arrays totalPair -= pairWithNum; } // Returning ans return totalPair; } // Driver Function function main() { const N = 5; const X = [3, 4, 4, 5, 1]; // Function call for printing result console.log(maxSubArrays(N, X)); } main(); |
9
Time Complexity: O(N)
Auxiliary Space: O(N), As HashMap is used to store frequencies.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!