1.6 C
New York
Wednesday, February 7, 2024

Minimal steps to succeed in finish by leaping to subsequent completely different bit as soon as

Share To Your Friends

[ad_1]

Given a binary array arr[] of dimension N which is ranging from index 0, the duty is to succeed in the top of the array within the minimal steps, motion throughout the array may be performed in 2 sorts of steps.

  • Type1: Transfer to the fast subsequent index having the identical worth.
  • Type2: Transfer to the fast subsequent index having a unique worth.

Observe: Kind 2 can be utilized simply as soon as whereas traversing.

Examples:

Enter: arr[] = {1, 0, 1, 0, 1}
Output: 2
Rationalization: Ranging from index 0 
First step: type1: 0->2
Second step: type1: 2->4

Enter: arr[] = {1, 0, 0, 0, 1, 0, 1, 0}
Output: 3
Rationalization: Ranging from index 0 
First step:  type1: 0->4
Second step: type1: 4->6
Third step: type2: 6->7

 

Strategy: The issue may be solved utilizing pre-computation method based mostly on the next thought:

To determine, from which sort of transfer we should always proceed, easy examine that the primary and final components are identical or not, if sure then merely proceed with kind 1 step in any other case discover an optimum place for switching with type2 stepping

Observe the steps to unravel the issue:

  • If first and final are identical then transfer with type1 steps solely and we are able to immediately print variety of steps by calculating variety of components having identical worth excluding first.
  • If first and final components are of various worth then discover an optimum place for switching with type2 stepping.
    • This may be performed by pre-computation for switching in any respect attainable indices.
    • Use 2 arrays X and Y, X holding variety of steps from begin (i.e complete occurrences of arr[0] from begin) whereas Y holding the variety of steps from finish (i.e. complete occurrences of arr[N-1] from the top).
    • The place switching is feasible, examine the full steps required and replace the minimal steps accordingly.
  • Return the minimal variety of steps required.

Under is the implementation for the above method:

C++

  

#embrace <bits/stdc++.h>

utilizing namespace std;

  

int Minstep(int arr[], int n)

{

    

    int c = arr[0], d = arr[n - 1];

  

    

    int x[n + 1], y[n + 1];

    x[0] = 0;

    y[n] = 0;

  

    

    

    

    for (int i = 1; i < n; i++) {

        if (arr[i] == c)

            x[i] = x[i - 1] + 1;

        else

            x[i] = x[i - 1];

    }

  

    

    

    if (arr[0] == arr[n - 1]) {

        return x[n - 1];

    }

  

    

    

    

    for (int i = n - 1; i >= 0; i--) {

        if (arr[i] == d)

            y[i] = y[i + 1] + 1;

        else

            y[i] = y[i + 1];

    }

  

    

    int ans = INT_MAX;

  

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

  

        

        

        

        

        if (arr[i] != c)

            proceed;

        ans = min(ans, x[i] + y[i + 1]);

    }

  

    

    return ans;

}

  

int fundamental()

{

    int N = 5;

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

  

    

    cout << Minstep(arr, N) << 'n';

    return 0;

}

Time Complexity: O(N)
Auxiliary Area: O(N)

[ad_2]


Share To Your Friends

Related Articles

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Latest Articles