Maximize score by rearranging Array

You are given an binary array (i.e., containing 0 and 1 as a element). Here, 0 means a straight path and 1 means zigzag path. Add one to score when zero appears otherwise do nothing. Find the contiguous maximum score that you can achieve from binary array. Calculate all ways of unique arrangement that you can achieve same maximum score.

Note – Rearranging elements of the binary array is possible.

Method of calculating score:
Contiguous maximum Score means:

n = 10, A[ ] = [1,0,1,0,0,0,1,0,0,1]

If we choose i from [4…6] then, i=4 then we add 1 to our score:

S=1 then i=5, S=1+2=3 then i=6, S=3+3=6

Or if we choose i=2 then our score S will be 1, or if we choose [8..9] our score will be i=8 S=1 then i=9 S will be 1+2=3. Our Max score from this array is 6 form [4…6].

Explanation:

n=10, A[ ]=[1,0,1,0,0,0,1,0,0,1]

(1). Here we can rearrange is possible so 1110000001 now from index [3…..8] maximum score will be 21.

(2). All unique arrangement that can give same maximum score, ans will be 5:
1) 1100000011
2) 1110000001
3) 1000000111
4) 0000001111
5) 1111000000

Approach:
For (1):
Sort the array all 0s will be together and all 1s will be together now for maximum score iterate from starting till 1 comes and take a count of zero and then answer will be (number of zeroes*(number of zeroes+1))/2. Time complexity is O(nlogn).

Optimization for (1) normally iterate from starting calculate number of 0s present and (number of zeroes*(number of zeroes+1))/2 will be the answer.
Time complexity is O(n).

For (2):
Here, we want same score which will give same score, it means we want all 0s contiguous to maintain our max score. So, here calculate all ones present in array and answer will be (total number of ones+1).

Even ones proof: 0001111 
1) 0001111 max score 6
2) 1111000 max score 6
3) 1000111 max score 6
4) 1100011 max score 6
5) 1110001 max score 6
Now, no other unique arrangement possible.

Odd ones proof: 00011111
1) 00011111 max score 6
2) 11111000 max score 6
3) 10001111 max score 6
4) 11110001 max score 6
5) 11000111 max score 6
6) 11100011 max score 6
Now, no other unique arrangement possible.

Implementation in C++:

#include<bits/stdc++.h>

using namespace std;
int ways_max_Score(int A[], int n) {
  int one = 0;
  for (int i = 0; i < n; i++) {
    if (A[i] == 1) {
      one++; //calculating number of ones	
    }
  }
  return one + 1;
}
int max_Score(int A[], int n) {
  int score = 0;
  sort(A, A + n); //sorting the array by which all 0s will come front
  for (int i = 0; i < n; i++) {
    if (A[i] == 0) {
      score += 1; //max score will number of zeros 
    }
  }
  score = (score * (score + 1)) / 2;
  return score;
}
int main() {
  int n = 10;
  int A[10]={1,0,1,0,0,0,1,0,0,1};
  cout << "Contiguous Max Score: " << max_Score(A, n) << endl;
  cout << "All Ways to get Max Score: " << ways_max_Score(A, n) << endl;
  return 0;
}

Output:

Contiguous Max Score: 21
All Ways to get Max Score: 5

Time complexity: O(nlogn)

Please write comments below if you find anything incorrect. A gentle request to share this topic on your social media profile.