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 HashMapdata 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:

// 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);
    }
}

9

Time Complexity: O(N) 
Auxiliary Space: O(N), As HashMap is used to store frequencies.

</div