Maximum elements which can be crossed using given units of a and b in C++

Given a binary array arr[] and two variables a and b with some initial values. To cross an element in the array arr[] there are two ways −

• If arr[i] == 1, then 1 unit can be used from a, with no change in b. If 1 unit is used from b, then a increases by 1 unit. (Note that the value of a cannot be incremented above its original value.)

• If arr[i] == 0, then 1 unit can be used from a or b.

Let’s now understand what we have to do using an example −

Input

arr[] = {0, 0, 0, 1, 1}, a = 2, b = 2

Output

5

Explanation

To cross 1^st element, use 1 unit from a (a = 1, b = 2).

To cross 2^nd element, use 1 unit from a (a = 0, b = 2).

To cross 3^rd element, use 1 unit from b (a = 0, b = 1).

To cross 4^th element, use 1 unit from b which increases a by 1 unit (a = 1, b = 0).

To cross 5^th element, use 1 unit from a (a = 0, b = 0).

Therefore, we crossed all elements and output becomes 5.

Input

arr[] = {1, 1, 1, 0, 1}, a = 1, b = 2

Output

4

Approach used in the below program as follows

• In function MaxElements() initialize variables Oa = 0 and max = 0, both of type int to store the original value of a and the final answer respectively.

• Loop from i = 0 till i<size to check for every element in the array.

• First Check if both a and b are equal to zero, then break out of the loop.

• Else check if (a == 0) and if so, then check if the current element = 1 and subtract 1 from b to cross that element and put a = min(Oa, a + 1) so that a does not exceed its original value.

  Else simply subtract 1 from b without affecting a.

• Else check if (b == 0) and if so, then simply subtract 1 from a.

• Else check if (arr[i] == 1 && a < Oa) and if so, then check if the current element = 1 and subtract 1 from b to cross that element and put a = min(Oa, a + 1).

• Else simply subtract 1 from a and increment max.

• Outside the loop, return max.

Example

 Live Demo

#include <bits/stdc++.h> using namespace std; int MaxElements(int arr[], int a, int b, int size){    // Oa will have original value of a    int Oa = a;    int max = 0;    // Iterate in the binary array    for (int i = 0; i < size; i++){       // Break loop if a and b, both are = 0       if (a == 0 && b == 0)          break;       // If a is not present, use b       else if (a == 0){          //increase a by 1 if arr[i] == 1          if (arr[i] == 1){             b -= 1;             //Checking if original value is not exceeded             a = min(Oa, a + 1);          }          else             b -= 1;       }       // If b is not present, use a       else if (b == 0)          a--;          // if arr[i] == 1,use b       else if (arr[i] == 1 && a < Oa){          b -= 1;          a = min(Oa, a + 1);       }       else          a--;          max++;    }    return max; } //main function int main(){    int arr[] = { 1, 1, 1, 0, 1 };    int size = sizeof(arr) / sizeof(arr[0]);    int a = 1;    int b = 2;    cout << MaxElements(arr, a, b, size);    return 0; }

Output

4