Physical Address

304 North Cardinal St.
Dorchester Center, MA 02124

Depend of distinct alternate triplets of indices from given Array | Set 2

[ad_1]

Given a binary array arr[] of measurement N, the duty is to search out the rely of distinct alternating triplets.

Be aware: A triplet is alternating if the values of these indices are in {0, 1, 0} or {1, 0, 1} type.

Examples:

Enter: arr[] = {0, 0, 1, 1, 0, 1} 
Output: 6
Clarification: Right here 4 sequence of “010” and two sequence of “101” exist. 
So, the entire variety of methods of alternating sequence of measurement 3 is 6.

Enter: arr[] = {0, 0, 0, 0, 0}
Output: 0
Clarification: As there aren’t any 1s within the array so we can’t discover any 3 measurement alternating sequence.

 

Naive Strategy: The naive method and the method primarily based on dynamic programming is talked about within the Set 1 of this text.

Environment friendly Strategy: This downside may be solved effectively utilizing prefix sum primarily based on the next concept:

  • The potential teams that may be shaped are {0, 1, 0} or {1, 0, 1}
  • So for any 1 encountered within the array the entire potential combos may be calculated by discovering the variety of methods to pick one 0 from its left and one 0 from its proper. This worth is similar because the product of variety of 0s to its left and the variety of 0s to its proper.
  • For a 0, the variety of potential triplets may be present in the identical means.
  • The ultimate reply is the sum of those two values.

Observe the beneath steps to resolve the issue:

  • Traverse the array ranging from the left and rely the variety of 0s in (say count1) and the entire variety of 1s (say count2). 
  • Then, initialize the left_count of each the numbers as 0.
  • Traverse the array from i = 0 to N:
    • Now, lets suppose 1 is encountered, so first calculate the combos of {0, 1, 0} potential utilizing this 1. For this, multiply left_count_Zero and count1 and add the outcome to our remaining reply. 
    • Add this worth with the sum.
    • Now, decrement the count2 as for the following ingredient it seems in left and thus, increment the left_count_One. 
    • Equally, do the identical when 0 is encountered.
  • Return the ultimate sum.

Beneath is the implementation for the above method:

C++

  

#embody <bits/stdc++.h>

utilizing namespace std;

  

lengthy lengthy numberOfWays(int A[], int N)

{

    int left_count_Zero = 0, count1 = 0;

    int left_count_One = 0, count2 = 0;

    lengthy lengthy ans = 0;

  

    

    

    for (int i = 0; i < N; i++) {

        if (A[i] == 1)

            count2++;

        else

            count1++;

    }

  

    

    for (int i = 0; i < N; i++) {

  

        

        

        

        if (A[i] == 1) {

  

            

            

            

            ans += (left_count_Zero * count1);

  

            

            

            left_count_One++;

            count2--;

        }

  

        

        

        

        else {

  

            

            

            

            

            ans += (left_count_One * count2);

  

            

            

            left_count_Zero++;

            count1--;

        }

    }

    return ans;

}

  

int major()

{

    int arr[] = { 0, 0, 1, 1, 0, 1 };

    int N = 6;

  

    

    cout << numberOfWays(arr, N);

    return 0;

}

Time Complexity: O(N)
Auxiliary House: O(1)

[ad_2]

Leave a Reply