Given an array arr[] of N elements. The task is to find the number of sub-sequences which have at least two consecutive elements such that absolute difference between them is ? 1.
Examples:
Input: arr[] = {1, 6, 2, 1}
Output: 6
{1, 2}, {1, 2, 1}, {2, 1}, {6, 2, 1}, {1, 1} and {1, 6, 2, 1}
are the sub-sequences that have at least one consecutive pair
with difference less than or equal to 1.Input: arr[] = {1, 6, 2, 1, 9}
Output: 12
Naive approach: The idea is to find all the possible sub-sequences and check if there exists a sub-sequence with any consecutive pair with difference ?1 and increase the count.
Efficient approach: The idea is to iterate over the given array and for each ith-element, try to find the required sub-sequence ending with ith element as its last element.
For every i, we want to use arr[i], arr[i] -1, arr[i] + 1, so we will define 2D array, dp[][], where dp[i][0] will contain the number of sub sequence that do not have any consecutive pair with difference less than 1 and dp[i][1] contain the number of sub sequence having any consecutive pair with difference ?1.
Also, we will maintain two variables required_subsequence and not_required_subsdequence to maintain the count of subsequences which have at least one consecutive element with difference ?1 and count of sub-sequences which do not contain any consecutive element pair with difference ?1.
Now, considering the sub-array arr[1] …. arr[i], we will perform the following steps:
- Compute the number of sub sequences which do not have any consecutive pair with difference less than 1 but will have by adding the ith element in the sub sequence. These are basically sum of dp[arr[i] + 1][0], dp[arr[i] – 1][0] and dp[arr[i]][0].
- Total number of subsequences have at least one consecutive pair with difference at least 1 and ending at i is equal to total sub-sequences found till i (just append arr[i] at the last) + subsequences which turns into subsequence have at least consecutive pair with difference less than 1 on adding arr[i].
- Total subsequence which do not have any consecutive pair with difference less than 1 and ending at i = total sub-sequence which do not have any consecutive pair with difference less than 1 before i + 1 (just the current element as a subsequence).
- Update required_sub-sequence, not_required_subsequence and dp[arr[i][0]] and the final answer will be required_subsequence.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;const int N = 10000;// Function to return the number of subsequences// which have at least one consecutive pair// with difference less than or equal to 1int count_required_sequence(int n, int arr[]){ int total_required_subsequence = 0; int total_n_required_subsequence = 0; int dp[N][2]; for (int i = 0; i < n; i++) { // Not required sub-sequences which // turn required on adding i int turn_required = 0; for (int j = -1; j <= 1; j++) turn_required += dp[arr[i] + j][0]; // Required sub-sequence till now will be // required sequence plus sub-sequence // which turns required int required_end_i = (total_required_subsequence + turn_required); // Similarly for not required int n_required_end_i = (1 + total_n_required_subsequence - turn_required); // Also updating total required and // not required sub-sequences total_required_subsequence += required_end_i; total_n_required_subsequence += n_required_end_i; // Also, storing values in dp dp[arr[i]][1] += required_end_i; dp[arr[i]][0] += n_required_end_i; } return total_required_subsequence;}// Driver codeint main(){ int arr[] = { 1, 6, 2, 1, 9 }; int n = sizeof(arr) / sizeof(int); cout << count_required_sequence(n, arr) << "\n"; return 0;} |
Java
// Java implementation of above approachpublic class GFG{ static int N = 10000;// Function to return the number of subsequences// which have at least one consecutive pair// with difference less than or equal to 1static int count_required_sequence(int n, int arr[]){ int total_required_subsequence = 0; int total_n_required_subsequence = 0; int [][]dp = new int[N][2]; for (int i = 0; i < n; i++) { // Not required sub-sequences which // turn required on adding i int turn_required = 0; for (int j = -1; j <= 1; j++) turn_required += dp[arr[i] + j][0]; // Required sub-sequence till now will be // required sequence plus sub-sequence // which turns required int required_end_i = (total_required_subsequence + turn_required); // Similarly for not required int n_required_end_i = (1 + total_n_required_subsequence - turn_required); // Also updating total required and // not required sub-sequences total_required_subsequence += required_end_i; total_n_required_subsequence += n_required_end_i; // Also, storing values in dp dp[arr[i]][1] += required_end_i; dp[arr[i]][0] += n_required_end_i; } return total_required_subsequence;}// Driver codepublic static void main(String[] args) { int arr[] = { 1, 6, 2, 1, 9 }; int n = arr.length; System.out.println(count_required_sequence(n, arr));}}// This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach import numpy as np;N = 10000; # Function to return the number of subsequences # which have at least one consecutive pair # with difference less than or equal to 1 def count_required_sequence(n, arr) : total_required_subsequence = 0; total_n_required_subsequence = 0; dp = np.zeros((N,2)); for i in range(n) : # Not required sub-sequences which # turn required on adding i turn_required = 0; for j in range(-1, 2,1) : turn_required += dp[arr[i] + j][0]; # Required sub-sequence till now will be # required sequence plus sub-sequence # which turns required required_end_i = (total_required_subsequence + turn_required); # Similarly for not required n_required_end_i = (1 + total_n_required_subsequence - turn_required); # Also updating total required and # not required sub-sequences total_required_subsequence += required_end_i; total_n_required_subsequence += n_required_end_i; # Also, storing values in dp dp[arr[i]][1] += required_end_i; dp[arr[i]][0] += n_required_end_i; return total_required_subsequence; # Driver code if __name__ == "__main__" : arr = [ 1, 6, 2, 1, 9 ]; n = len(arr); print(count_required_sequence(n, arr)) ; # This code is contributed by AnkitRai01 |
C#
using System;public class GFG{ static int N = 10000; // Function to return the number of subsequences// which have at least one consecutive pair// with difference less than or equal to 1static int count_required_sequence(int n, int[] arr){ int total_required_subsequence = 0; int total_n_required_subsequence = 0; int [,]dp = new int[N,2]; for (int i = 0; i < n; i++) { // Not required sub-sequences which // turn required on adding i int turn_required = 0; for (int j = -1; j <= 1; j++) turn_required += dp[arr[i] + j,0]; // Required sub-sequence till now will be // required sequence plus sub-sequence // which turns required int required_end_i = (total_required_subsequence + turn_required); // Similarly for not required int n_required_end_i = (1 + total_n_required_subsequence - turn_required); // Also updating total required and // not required sub-sequences total_required_subsequence += required_end_i; total_n_required_subsequence += n_required_end_i; // Also, storing values in dp dp[arr[i],1] += required_end_i; dp[arr[i],0] += n_required_end_i; } return total_required_subsequence;} // Driver code static public void Main () { int[] arr = { 1, 6, 2, 1, 9 }; int n = arr.Length; Console.WriteLine(count_required_sequence(n, arr)); }}// This code is contributed by rag2127. |
Javascript
<script>// Javascript implementation of the approachvar N = 10000;// Function to return the number of subsequences// which have at least one consecutive pair// with difference less than or equal to 1function count_required_sequence(n, arr){ var total_required_subsequence = 0; var total_n_required_subsequence = 0; var dp = Array.from(Array(N), ()=> Array(2).fill(0)); for (var i = 0; i < n; i++) { // Not required sub-sequences which // turn required on adding i var turn_required = 0; for (var j = -1; j <= 1; j++) turn_required += dp[arr[i] + j][0]; // Required sub-sequence till now will be // required sequence plus sub-sequence // which turns required var required_end_i = (total_required_subsequence + turn_required); // Similarly for not required var n_required_end_i = (1 + total_n_required_subsequence - turn_required); // Also updating total required and // not required sub-sequences total_required_subsequence += required_end_i; total_n_required_subsequence += n_required_end_i; // Also, storing values in dp dp[arr[i]][1] += required_end_i; dp[arr[i]][0] += n_required_end_i; } return total_required_subsequence;}// Driver codevar arr = [ 1, 6, 2, 1, 9 ];var n = arr.length;document.write( count_required_sequence(n, arr) + "<br>");</script> |
Output:
12
Time Complexity: O(N), where N represents the size of the given array.
Auxiliary Space: O(N), where N represents the size of the given array.
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!
