Given an array arr[] containing integers. The task is to find the number of decreasing subarrays with a difference of 1.
Examples:
Input: arr[] = {3, 2, 1, 4}
Output: 7
Explanation: Following are the possible decreasing subarrays with difference 1.
[3], [2], [1], [4], [3,2], [2,1], and [3,2,1]
Therefore, the answer is 7.Input: arr[] = {5, 4, 3, 2, 1, 6}
Output: 16
Naive Approach: This problem can be solved by using Dynamic Programming. Follow the steps below to solve the given problem.
- For every index i the task is to calculate number of subarrays ending at i which follows this pattern arr[i-2]==arr[i-1]+1, arr[i-1]==arr[i]+1.
- Initialize a variable say ans = 0, to store the number of decreasing subarrays with a difference of 1.
- We can make a dp[] array which stores the count of these continuous elements for every index.
- dp[i] is the number of subarrays ending at i which follows this pattern.
- Traverse dp[] and add each value in ans.
- Return ans as the final result.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to count number of// decreasing subarrays with difference 1long long getcount(vector<int>& p){ int size = p.size(), cnt = 0; long long ans = 0; vector<int> dp(size, cnt); for (int i = 0; i < size; i++) { if (i == 0) cnt = 1; else if (p[i] + 1 == p[i - 1]) cnt++; else cnt = 1; dp[i] = cnt; } for (int i = 0; i < size; i++) ans += dp[i]; return ans;}// Driver Codeint main(){ vector<int> arr{ 5, 4, 3, 2, 1, 6 }; // Function Call cout << getcount(arr); return 0;} |
Java
// Java code to implement the above approachimport java.util.*;public class GFG{ // Function to count number of // decreasing subarrays with difference 1 static long getcount(int p[]) { int size = p.length, cnt = 0; long ans = 0; int dp[] = new int[size]; for(int i = 0; i < size; i++) { dp[i] = cnt; } for (int i = 0; i < size; i++) { if (i == 0) cnt = 1; else if (p[i] + 1 == p[i - 1]) cnt++; else cnt = 1; dp[i] = cnt; } for (int i = 0; i < size; i++) ans += dp[i]; return ans; } // Driver code public static void main(String args[]) { int arr[] = { 5, 4, 3, 2, 1, 6 }; // Function Call System.out.println(getcount(arr)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code to implement the above approach# Function to count number of# decreasing subarrays with difference 1def getcount(p): size = len(p) cnt = 0 ans = 0 dp = [cnt for i in range(size)] for i in range(size): if (i == 0): cnt = 1 elif (p[i] + 1 == p[i - 1]): cnt += 1 else: cnt = 1 dp[i] = cnt for i in range(size): ans += dp[i] return ans# Driver Codearr = [5, 4, 3, 2, 1, 6]# Function Callprint(getcount(arr))# This code is contributed by Shubham Singh |
C#
// C# code to implement the above approachusing System;class GFG{ // Function to count number of // decreasing subarrays with difference 1 static long getcount(int []p) { int size = p.Length, cnt = 0; long ans = 0; int []dp = new int[size]; for(int i = 0; i < size; i++) { dp[i] = cnt; } for (int i = 0; i < size; i++) { if (i == 0) cnt = 1; else if (p[i] + 1 == p[i - 1]) cnt++; else cnt = 1; dp[i] = cnt; } for (int i = 0; i < size; i++) ans += dp[i]; return ans; } // Driver code public static void Main() { int []arr = { 5, 4, 3, 2, 1, 6 }; // Function Call Console.Write(getcount(arr)); }}// This code is contributed by Samim Hossain Mondal. |
Javascript
<script>// JavaScript program for above approach // Function to count number of decreasing// subarrays with difference 1function getcount(p){ let size = p.length, cnt = 0; let ans = 0; let dp = new Array(size).fill(cnt); for(let i = 0; i < size; i++) { if (i == 0) cnt = 1; else if (p[i] + 1 == p[i - 1]) cnt++; else cnt = 1; dp[i] = cnt; } for(let i = 0; i < size; i++) ans += dp[i]; return ans;}// Driver Codelet arr = [ 5, 4, 3, 2, 1, 6 ];// Function Calldocument.write(getcount(arr));// This code is contributed by Potta Lokesh</script> |
Output
16
Time complexity: O(N)
Auxiliary Space: O(N)
Efficient Approach: In the above approach the auxiliary space complexity can be further optimized to constant space by replacing dp[] array with a variable to keep track of the current number of subarrays. Follow the steps below to solve the given problem.
- Initialize a variable say count = 0.
- Start traversing the array when arr[i]-arr[i-1 ]==1 to make a chain of numbers that are decreasing by 1, then count++.
- Add the count to the ans.
- When the chain breaks that means, arr[i]-arr[i-1] !=1 then reset the count.
- Return ans as the final result.
Below is the implementation of the above approach.
C++
// C++ program for above approach#include <bits/stdc++.h>using namespace std;// Function to count the number of// decreasing subarrays with difference 1long long getcount(vector<int>& arr){ long long int ans = arr.size(); long long int count = 0; for (int i = 1; i < arr.size(); i++) { if (arr[i - 1] - arr[i] == 1) count++; else count = 0; ans = ans + count; } return ans;}// Driver Codeint main(){ vector<int> arr{ 5, 4, 3, 2, 1, 6 }; // Function Call cout << getcount(arr); return 0;} |
Java
// Java program for above approachclass GFG{ // Function to count the number of // decreasing subarrays with difference 1 static long getcount(int[] arr) { int ans = arr.length; int count = 0; for (int i = 1; i < arr.length; i++) { if (arr[i - 1] - arr[i] == 1) count++; else count = 0; ans = ans + count; } return ans; } // Driver Code public static void main(String[] args) { int[] arr = { 5, 4, 3, 2, 1, 6 }; // Function Call System.out.print(getcount(arr)); }}// This code is contributed by 29AjayKumar |
Python3
#Python program for the above approach# Function to count the number of# decreasing subarrays with difference 1def getcount(arr): ans = len(arr) count = 0 for i in range(1, len(arr)): if (arr[i - 1] - arr[i] == 1): count+=1 else: count = 0 ans = ans + count return ans # Driver Codearr = [ 5, 4, 3, 2, 1, 6 ]# Function Callprint(getcount(arr))# This code is contributed by Shubham Singh |
C#
// C# program for above approachusing System;public class GFG{ // Function to count the number of // decreasing subarrays with difference 1 static long getcount(int[] arr) { int ans = arr.Length; int count = 0; for (int i = 1; i < arr.Length; i++) { if (arr[i - 1] - arr[i] == 1) count++; else count = 0; ans = ans + count; } return ans; } // Driver Code public static void Main(String[] args) { int[] arr = { 5, 4, 3, 2, 1, 6 }; // Function Call Console.Write(getcount(arr)); }}// This code is contributed by 29AjayKumar |
Javascript
<script>// javascript program for above approach // Function to count the number of // decreasing subarrays with difference 1 function getcount(arr) { var ans = arr.length; var count = 0; for (var i = 1; i < arr.length; i++) { if (arr[i - 1] - arr[i] == 1) count++; else count = 0; ans = ans + count; } return ans; } // Driver Codevar arr = [ 5, 4, 3, 2, 1, 6 ];// Function Calldocument.write(getcount(arr));// This code is contributed by 29AjayKumar </script> |
Output
16
Time complexity: O(N)
Auxiliary Space: O(1)
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!
