Mock Canadian Computing Competition: 2026 Junior #4

Dr. Bronstein is a famous scientist that does top-secret research. He keeps all of his most prized and the secretive research done in a hidden vault in the basement of a library, which is closed off by a giant vault door.

The vault door is circular, and acts like a large combination lock. There are ~N~ numerical bits that appear along the circumference, each either a ~1~ or ~0~. Specifically, the ~i^\text{th}~ bit is adjacent to the ~(i-1)^\text{th}~ and ~(i+1)^\text{th}~ bit, with the ~N^\text{th}~ being adjacent to the ~1^\text{st}~.

In order for the vault to open, the following conditions must be met:

• each ~1~ bit must be directly adjacent to an odd number of ~1~ bits
• each ~0~ bit must be directly adjacent to an even number of ~0~ bits

What is the minimum number of bit flips needed such that the vault will open?

Input Specification

The first line contains a single integer ~N~, the number of bits.

The next line contains a string of ~N~ bits, each being ~0~ or ~1~, indicating the initial state of bits on the combination lock.

The following table shows how the available 15 marks are distributed.

Marks	Bounds on ~N~	Description
~5~ marks	~3 \le N \le 10~	The number of bits are small
~5~ marks	~3 \le N \le 100~	At most ~2~ bitflips will be required.
~5~ marks	~3 \le N \le 100\,000~	The number of bits are large

Output Specification

Output the number of bits that need to be flipped in order for the vault to open.

Sample Input 1

6
101110

Output for Sample Input 1

2

Explanation of Output for Sample Input 1

By flipping the ~5^\text{th}~ and ~6^\text{th}~ bits, we get 101110 ~\rightarrow~ 101101, where the new set of bits allow for the gate to be open.

It can be shown that ~2~ bit flips are the minimum needed.

Sample Input 2

4
1000

Output for Sample Input 2

1

Explanation of Output for Sample Input 2

By flipping the ~1^\text{st}~ bit, we get 1000 ~\rightarrow~ 0000, where the new set of bits allow for the gate to be open.