All Tracks Basic Programming Bit Manipulation Basics of Bit Manipulation Problem

Monk and Binary Array
Tag(s):

Ad-Hoc, Bit manipulation, Easy-Medium

Problem
Editorial
Analytics

After a long break, Monk is going to start his practice for ACM ICPC. He is scared of binary arrays (arrays consisting of only \(0's\) and \(1's\) ). For the same reason, he starts solving a problem involving binary arrays. He is given a binary array of N elements consisting of only \(0's\) and \(1's\). He needs to perform exactly one operation in which he can flip the value of exactly one element of the array, i.e, change 0 to 1 or 1 to 0.

After performing the operation, he needs to maximize the count of all sub arrays exclusive-OR of whose elements is 1. Monk cannot do the problem on his own so he needs your help. Please help him as he does not want to lose motivation at the very beginning of his preparation for ACM ICPC.

Input Format:

The first line contains a single integer N denoting the size of binary array.

The next line contains N space separated integers denoting the elements of the array. Each element can take values either 0 or 1.

Output Format:

Output a single integer denoting the maximum count of sub arrays exclusive-OR of whose elements is 1.

Constraints:

  • \(1 \le N \le 2000 \)
  • \(0 \le A[i] \le 1 \)
SAMPLE INPUT
3
1 0 0
SAMPLE OUTPUT
4

Explanation

In the given test case, the best answer is possible if we change the last element to 1. The array will become 1 0 1 and hence the answer will be 4.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (CheckPoint III)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?