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 codeint 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 approachimport 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 codeif __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 approachusing 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 codevar 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)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
