Given an array arr[] of N integers. The task is to count the total number of subarrays of the given array such that the difference between the consecutive elements in the subarrays is one. That is, for any index 
in the subarrays, arr[i+1] – arr[i] = 1.
Note: Do not consider subarrays with a single element.
Examples:
Input : arr[] = {1, 2, 3}
Output : 3
The subarrays are {1, 2}. {2, 3} and {1, 2, 3}
Input : arr[] = {1, 2, 3, 5, 6, 7}
Output : 6
Naive Approach: A simple approach is to run two nested loops and check every subarray and calculate the count of subarrays with consecutive elements differing by 1.
C++
#include <iostream>using namespace std;int countSubarrays(int arr[], int n) { int count = 0; // Initialize count to 0 // Loop over all subarrays for (int i = 0; i < n; i++) { int j = i + 1; // Check if consecutive elements differ by 1 while (j < n && arr[j] - arr[j-1] == 1) { j++; } // Add the count of subarrays with consecutive elements differing by 1 count += (j - i) * (j - i - 1) / 2; // Move i to the next position i = j - 1; } // Return the total count of subarrays return count;}int main() { int arr[] = {1, 2, 3}; int n = sizeof(arr)/sizeof(arr[0]); int count = countSubarrays(arr, n); cout << "Total number of subarrays with consecutive elements differing by 1: " << count << endl; return 0;}// This code is contributed by Naveen Gujjar. |
Java
import java.util.*;public class Main { public static int countSubarrays(int[] arr, int n) { int count = 0; // Initialize count to 0 // Loop over all subarrays for (int i = 0; i < n; i++) { int j = i + 1; // Check if consecutive elements differ by 1 while (j < n && arr[j] - arr[j-1] == 1) { j++; } // Add the count of subarrays with consecutive elements differing by 1 count += (j - i) * (j - i - 1) / 2; // Move i to the next position i = j - 1; } // Return the total count of subarrays return count; } public static void main(String[] args) { int[] arr = {1, 2, 3}; int n = arr.length; int count = countSubarrays(arr, n); System.out.println("Total number of subarrays with consecutive elements differing by 1: " + count); }} |
Python3
def countSubarrays(arr, n): count = 0 # Initialize count to 0 # Loop over all subarrays i = 0 while i < n: j = i + 1 # Check if consecutive elements differ by 1 while j < n and arr[j] - arr[j-1] == 1: j += 1 # Add the count of subarrays with consecutive elements differing by 1 count += (j - i) * (j - i - 1) // 2 # Move i to the next position i = j # Return the total count of subarrays return countarr = [1, 2, 3]n = len(arr)count = countSubarrays(arr, n)print("Total number of subarrays with consecutive elements differing by 1:", count) |
C#
using System;class Gfg{ static int countSubarrays(int[] arr, int n) { int count = 0; // Initialize count to 0 // Loop over all subarrays for (int i = 0; i < n; i++) { int j = i + 1; // Check if consecutive elements differ by 1 while (j < n && arr[j] - arr[j-1] == 1) { j++; } // Add the count of subarrays with consecutive elements differing by 1 count += (j - i) * (j - i - 1) / 2; // Move i to the next position i = j - 1; } // Return the total count of subarrays return count; } public static void Main() { int[] arr = {1, 2, 3}; int n = arr.Length; int count = countSubarrays(arr, n); Console.WriteLine("Total number of subarrays with consecutive elements differing by 1: " + count); }} |
Javascript
function countSubarrays(arr, n) { let count = 0; // Initialize count to 0 // Loop over all subarrays for (let i = 0; i < n; i++) { let j = i + 1; // Check if consecutive elements differ by 1 while (j < n && arr[j] - arr[j - 1] === 1) { j++; } // Add the count of subarrays with consecutive elements differing by 1 count += ((j - i) * (j - i - 1)) / 2; // Move i to the next position i = j - 1; } // Return the total count of subarrays return count;}const arr = [1, 2, 3];const n = arr.length;const count = countSubarrays(arr, n);console.log( `Total number of subarrays with consecutive elements differing by 1: ${count}`); |
Output
Total number of subarrays with consecutive elements differing by 1: 3
Time Complexity: O(N²)
Auxiliary Space: O(1)
Efficient Approach: An efficient approach is to observe that in an array of length say K, the total number of subarrays of size greater than 1 = (K)*(K-1)/2.
So, the idea is to traverse the array by using two pointers to calculate subarrays with consecutive elements in a window of maximum length and then calculate all subarrays in that window using the above formula.
Below is the step-by-step algorithm:
- Take two pointers to say fast and slow, for maintaining a window of consecutive elements.
- Start traversing the array.
- If elements differ by 1 increment only the fast pointer.
- Else, calculate the length of the current window between the indexes fast and slow.
Below is the implementation of the given approach:
C++
// C++ program to count Subarrays with// Consecutive elements differing by 1#include <iostream>using namespace std;// Function to count Subarrays with// Consecutive elements differing by 1int subarrayCount(int arr[], int n){ // Variable to store count of subarrays // whose consecutive elements differ by 1 int result = 0; // Take two pointers for maintaining a // window of consecutive elements int fast = 0, slow = 0; // Traverse the array for (int i = 1; i < n; i++) { // If elements differ by 1 // increment only the fast pointer if (arr[i] - arr[i - 1] == 1) { fast++; } else { // Calculate length of subarray int len = fast - slow + 1; // Calculate total subarrays except // Subarrays with single element result += len * (len - 1) / 2; // Update fast and slow fast = i; slow = i; } } // For last iteration. That is if array is // traversed and fast > slow if (fast != slow) { int len = fast - slow + 1; result += len * (len - 1) / 2; } return result;}// Driver Codeint main(){ int arr[] = { 1, 2, 3, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); cout << subarrayCount(arr, n); return 0;} |
Java
// Java program to count Subarrays with// Consecutive elements differing by 1class cfg {// Function to count Subarrays with// Consecutive elements differing by 1static int subarrayCount(int arr[], int n){ // Variable to store count of subarrays // whose consecutive elements differ by 1 int result = 0; // Take two pointers for maintaining a // window of consecutive elements int fast = 0, slow = 0; // Traverse the array for (int i = 1; i < n; i++) { // If elements differ by 1 // increment only the fast pointer if (arr[i] - arr[i - 1] == 1) { fast++; } else { // Calculate length of subarray int len = fast - slow + 1; // Calculate total subarrays except // Subarrays with single element result += len * (len - 1) / 2; // Update fast and slow fast = i; slow = i; } } // For last iteration. That is if array is // traversed and fast > slow if (fast != slow) { int len = fast - slow + 1; result += len * (len - 1) / 2; } return result;}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 2, 3, 5, 6, 7 }; int n = arr.length; System.out.println(subarrayCount(arr, n));}}//This code is contributed by Mukul Singh |
Python3
# Python3 program to count Subarrays with # Consecutive elements differing by 1 # Function to count Subarrays with # Consecutive elements differing by 1 def subarrayCount(arr, n) : # Variable to store count of subarrays # whose consecutive elements differ by 1 result = 0 # Take two pointers for maintaining a # window of consecutive elements fast, slow = 0, 0 # Traverse the array for i in range(1, n) : # If elements differ by 1 # increment only the fast pointer if (arr[i] - arr[i - 1] == 1) : fast += 1 else : # Calculate length of subarray length = fast - slow + 1 # Calculate total subarrays except # Subarrays with single element result += length * (length - 1) // 2; # Update fast and slow fast = i slow = i # For last iteration. That is if array is # traversed and fast > slow if (fast != slow) : length = fast - slow + 1 result += length * (length - 1) // 2; return result# Driver Code if __name__ == "__main__" : arr = [ 1, 2, 3, 5, 6, 7 ] n = len(arr) print(subarrayCount(arr, n))# This code is contributed by Ryuga |
C#
// C# program to count Subarrays with// Consecutive elements differing by 1using System;class cfg {// Function to count Subarrays with// Consecutive elements differing by 1static int subarrayCount(int []arr, int n){ // Variable to store count of subarrays // whose consecutive elements differ by 1 int result = 0; // Take two pointers for maintaining a // window of consecutive elements int fast = 0, slow = 0; // Traverse the array for (int i = 1; i < n; i++) { // If elements differ by 1 // increment only the fast pointer if (arr[i] - arr[i - 1] == 1) { fast++; } else { // Calculate length of subarray int len = fast - slow + 1; // Calculate total subarrays except // Subarrays with single element result += len * (len - 1) / 2; // Update fast and slow fast = i; slow = i; } } // For last iteration. That is if array is // traversed and fast > slow if (fast != slow) { int len = fast - slow + 1; result += len * (len - 1) / 2; } return result;}// Driver Codepublic static void Main(){ int []arr = { 1, 2, 3, 5, 6, 7 }; int n = arr.Length; Console.WriteLine(subarrayCount(arr, n));}}//This code is contributed by inder_verma.. |
PHP
<?php// PHP program to count Subarrays with// Consecutive elements differing by 1// Function to count Subarrays with// Consecutive elements differing by 1function subarrayCount($arr, $n){ // Variable to store count of subarrays // whose consecutive elements differ by 1 $result = 0; // Take two pointers for maintaining a // window of consecutive elements $fast = 0; $slow = 0; // Traverse the array for ($i = 1; $i < $n; $i++) { // If elements differ by 1 // increment only the fast pointer if ($arr[$i] - $arr[$i - 1] == 1) { $fast++; } else { // Calculate length of subarray $len = $fast - $slow + 1; // Calculate total subarrays except // Subarrays with single element $result += $len * ($len - 1) / 2; // Update fast and slow $fast = $i; $slow = $i; } } // For last iteration. That is if array // is traversed and fast > slow if ($fast != $slow) { $len = $fast - $slow + 1; $result += $len * ($len - 1) / 2; } return $result;}// Driver Code$arr = array(1, 2, 3, 5, 6, 7);$n = sizeof($arr);echo subarrayCount($arr, $n);// This code is contributed // by Akanksha Rai?> |
Javascript
<script>// Javascript program to count Subarrays with// Consecutive elements differing by 1 // Function to count Subarrays with // Consecutive elements differing by 1 function subarrayCount(arr , n) { // Variable to store count of subarrays // whose consecutive elements differ by 1 var result = 0; // Take two pointers for maintaining a // window of consecutive elements var fast = 0, slow = 0; // Traverse the array for (i = 1; i < n; i++) { // If elements differ by 1 // increment only the fast pointer if (arr[i] - arr[i - 1] == 1) { fast++; } else { // Calculate length of subarray var len = fast - slow + 1; // Calculate total subarrays except // Subarrays with single element result += len * (len - 1) / 2; // Update fast and slow fast = i; slow = i; } } // For last iteration. That is if array is // traversed and fast > slow if (fast != slow) { var len = fast - slow + 1; result += len * (len - 1) / 2; } return result; } // Driver Code var arr = [ 1, 2, 3, 5, 6, 7 ]; var n = arr.length; document.write(subarrayCount(arr, n));// This code contributed by aashish1995</script> |
Output
6
Complexity Analysis:
- Time Complexity: O(N), as we are using a loop to traverse N times so the complexity for the program will be O(N).
- Auxiliary Space: O(1), as we are not using any extra space.
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!
