[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->4Enter: 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++
|
|
Time Complexity: O(N)
Auxiliary Area: O(N)
[ad_2]