Count of distinct alternating triplets of indices from given Array
Given a binary array arr[] of size N, the task is to find the count of distinct alternating triplets.
Note: A triplet is alternating if the values of those indices are in {0, 1, 0} or {1, 0, 1} form.
Examples:
Input: arr[] = {0, 0, 1, 1, 0, 1}
Output: 6
Explanation: Here four sequence of “010” and two sequence of “101” exist.
So, the total number of ways of alternating sequence of size 3 is 6.Input: arr[] = {0, 0, 0, 0, 0}
Output: 0
Explanation: As there are no 1s in the array so we cannot find any 3 size alternating sequence.
Naive approach: The basic idea to solve this problem is as follows:
Find all the triplets and check which among those follow the alternating property.
Follow the steps mentioned below to implement the idea:
- Use three nested loops to point i, j, k such that (i < j < k).
- Check if arr[i] < arr[j] > arr[k] or arr[i] > arr[j] < arr[k].
- If so then increment the answer.
- Otherwise, continue the iteration.
- Return the final count of triplets.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient approach: This problem can be solved efficiently using dynamic programming based on the following idea:
The count of alternating subsequences ending at jth index having size i is the same as the sum of values of all the subsequences having size i-1 and having value different from arr[j].
So dynamic programming concept can be utilised here.
To utilise the dynamic programming concept, form a dp[][] array where dp[i][j] stores the count of the alternating subsequence with size i and ending at jth index. Here i cannot exceed 3 because we need to find triplets.
Follow the steps mentioned below to implement the idea:
- Declare a 2D array (say dp[][]) having (4 rows) and (N + 1 columns) and initialize it with value 0.
- Iterate from i = 1 to 3 for possible subsequence lengths:
- Now iterate from j = 0 to N-1 (considering j is the last index of such a subsequence):
- If the size of sequence is 1 or say (i == 1) then dp[i][j] = 1 because there is only one way to create a 1 size sequence with one element.
- Otherwise, iterate from k = 0 till j to find any previous element which is different from arr[j].
- If exist, then add dp[i][k] to dp[i][j].
- Now iterate from j = 0 to N-1 (considering j is the last index of such a subsequence):
- Return the number of possible triplets which is same as the sum of the values stored at the row dp[3][j].
Below is the implementation of the above approach:
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to find the distinct ways to // find alternate sequence of size 3. long long numberOfWays(vector< int >& s, int n) { int size = 3; long long ans = 0; // Declaring a 2d dp vector<vector< long long > > dp(size + 1, vector< long long >( n + 1, 0)); for ( int i = 1; i <= size; i++) { for ( int j = 0; j < n; j++) { // Filling the first row with 1. if (i == 1) { dp[i][j] = 1; } else { // Finding the sum of // all sequences // which are ending with // alternate number for ( int k = 0; k < j; k++) { if (s[k] != s[j]) { dp[i][j] += dp[i - 1][k]; } } } } } // Answer is the sum of last row of dp for ( int i = 0; i < n; i++) { ans += dp[size][i]; } return ans; } // Driver code int main() { vector< int > arr = { 0, 0, 1, 1, 0, 1 }; int N = arr.size(); cout << numberOfWays(arr, N); return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to find the distinct ways to // find alternate sequence of size 3. public static long numberOfWays( int s[], int n) { int size = 3 ; long ans = 0 ; // Declaring a 2d dp long dp[][] = new long [size + 1 ][n + 1 ]; for ( int i = 1 ; i <= size; i++) { for ( int j = 0 ; j < n; j++) { // Filling the first row with 1. if (i == 1 ) { dp[i][j] = 1 ; } else { // Finding the sum of // all sequences // which are ending with // alternate number for ( int k = 0 ; k < j; k++) { if (s[k] != s[j]) { dp[i][j] += dp[i - 1 ][k]; } } } } } // Answer is the sum of last row of dp for ( int i = 0 ; i < n; i++) { ans += dp[size][i]; } return ans; } public static void main(String[] args) { int arr[] = { 0 , 0 , 1 , 1 , 0 , 1 }; int N = arr.length; System.out.print(numberOfWays(arr, N)); } } // This code is contributed by Rohit Pradhan |
Python3
# Python program for above approach # Function to find the distinct ways to # find alternate sequence of size 3. def numberOfWays(s, n) : size = 3 ans = 0 # Declaring a 2d dp dp = [[ 0 ] * (n + 1 )] * (size + 1 ) for i in range ( 1 , size - 1 , 1 ) : for j in range ( 0 , n, 1 ) : # Filling the first row with 1. if (i = = 1 ) : dp[i][j] = 1 else : # Finding the sum of # all sequences # which are ending with # alternate number for k in range ( 0 , j, 1 ) : if (s[k] ! = s[j]) : dp[i][j] + = dp[i - 1 ][k] # Answer is the sum of last row of dp for i in range ( 0 , n) : ans + = dp[size][i] return ans # Driver code if __name__ = = "__main__" : arr = [ 0 , 0 , 1 , 1 , 0 , 1 ] N = len (arr) print (numberOfWays(arr, N)) # This code is contributed by code_hunt. |
C#
// C# code to implement the approach using System; public class GFG{ // Function to find the distinct ways to // find alternate sequence of size 3. public static long numberOfWays( int [] s, int n) { int size = 3; long ans = 0; // Declaring a 2d dp long [,] dp = new long [size + 1,n + 1]; for ( int i = 1; i <= size; i++) { for ( int j = 0; j < n; j++) { // Filling the first row with 1. if (i == 1) { dp[i, j] = 1; } else { // Finding the sum of // all sequences // which are ending with // alternate number for ( int k = 0; k < j; k++) { if (s[k] != s[j]) { dp[i, j] += dp[i - 1, k]; } } } } } // Answer is the sum of last row of dp for ( int i = 0; i < n; i++) { ans += dp[size, i]; } return ans; } static public void Main (){ int [] arr = { 0, 0, 1, 1, 0, 1 }; int N = arr.Length; Console.Write(numberOfWays(arr, N)); } } // This code is contributed by hrithikgarg03188. |
Javascript
<script> // JS code to implement the approach // Function to find the distinct ways to // find alternate sequence of size 3. function numberOfWays(s, n) { var size = 3; var ans = 0; // Declaring a 2d dp var dp = []; for ( var i = 0; i <= size; i++) { dp.push([]); for ( var j = 0; j <= n; j++) dp[i].push(0); } for ( var i = 1; i <= size; i++) { for ( var j = 0; j < n; j++) { // Filling the first row with 1. if (i == 1) { dp[i][j] = 1; } else { // Finding the sum of // all sequences // which are ending with // alternate number for ( var k = 0; k < j; k++) { if (s[k] != s[j]) { dp[i][j] += dp[i - 1][k]; } } } } } // Answer is the sum of last row of dp for ( var i = 0; i < n; i++) { ans += dp[size][i]; } return ans; } // Driver code var arr = [ 0, 0, 1, 1, 0, 1 ]; var N = arr.length; document.write(numberOfWays(arr, N)); // This code is contributed by phasing17 </script> |
6
Time Complexity: O(N2)
Auxiliary Space: O(N)