Given a binary array arr[] of size N and an integer K, the task is to find the highest index which can be reached in exactly K jumps starting from first index, when one jump can be made between indices having different values.
Examples:
Input: arr[] = {0, 1, 1, 0, 1, 0}, K = 2
Output: 5
Explanation: All possible jumps are:
{0, 1, 3}, {0, 2, 3}, {0, 1, 5}, {0, 2, 5}, {0, 4, 5}
So, the highest index that can be reached is index 5.Input: arr[] = {1, 0, 1, 1, 0}, K = 3
Output: 4
Approach: The problem can be solved based on the following observation:
- The highest possible value of K is same as the total number of shifts between consecutive 1s and consecutive 0s.
- As in a jump, the two values are different, so if K is even then the value at starting index and value at last index will be same and if K is odd ten they will be different.
- Now to find the highest index (when it is posssible to make K jumps), iterate from end of array and based on K being even or odd return the first index i such that arr[i] = arr[0] or arr[i] ≠ arr[0] (because it is already found that a total of K jumps can be made between them).
Given below is an illustration for better understanding:
Illustration:
Consider arr[] = {0, 1, 1, 0, 1, 0}, K = 2.
Highest possible value of K = 4:
=> Consecutive 0s in range [0, 0]. Total shifts = 0
=> Consecutive 1s in range [1, 2]. Shift from consecutive 0s to 1s. Total shifts = 1.
=> Consecutive 0s in range [3, 3]. Shift from consecutive 1s to 0s. Total shifts = 1+1 = 2.
=> Consecutive 1s in range [4, 4]. Shift from consecutive 0s to 1s. Total shifts = 2+1 = 3.
=> Consecutive 0s in range [5, 5]. Shift from consecutive 1s to 0s. Total shifts = 3+1 = 4.Iterate from i = 5 to 0:
=>For i = 5: arr[5] = arr[0] = 0. K = 2 i.e. even. Stop iterating
Highest index that can be reached is 5.One such path is (0->1->5).
Follow the steps mentioned below to solve the problem:
- Traverse the array from i = 0 to N-1:
- Find total shifts from consecutive 0s to consecutive 1s and vice versa (say count).
- If K > count, return -1 as K jumps is not possible.
- Otherwise, traverse from i = N-1 to 0:
- If K is even, stop iteration when arr[i] = arr[0].
- If K is odd, stop iteration when arr[i] ≠ arr[0].
- Return the highest index achieved from the above step.
Below is the implementation of the above approach:
C++
|
Time complexity: O(N)
Auxiliary Space: O(N)