Unequal Array (Codeforces 1672C)
Tags: Greedy, implementation

You are given an array $$$a$$$ of length $$$n$$$. We define the equality of the array as the number of indices $$$1 \le i \le n - 1$$$ such that $$$a_i = a_{i + 1}$$$. We are allowed to do the following operation:  Select two integers $$$i$$$ and $$$x$$$ such that $$$1 \le i \le n - 1$$$ and $$$1 \le x \le 10^9$$$. Then, set $$$a_i$$$ and $$$a_{i + 1}$$$ to be equal to $$$x$$$. Find the minimum number of operations needed such that the equality of the array is less than or equal to $$$1$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10 ^ 5$$$) — the length of array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — elements of the array.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10 ^ 5$$$

Output: For each test case, print the minimum number of operations needed.

Note: In the first test case, we can select $$$i=2$$$ and $$$x=2$$$ to form $$$[1, 2, 2, 1, 1]$$$. Then, we can select $$$i=3$$$ and $$$x=3$$$ to form $$$[1, 2, 3, 3, 1]$$$.In the second test case, we can select $$$i=3$$$ and $$$x=100$$$ to form $$$[2, 1, 100, 100, 2]$$$.

Sample Inputs:
4
5
1 1 1 1 1
5
2 1 1 1 2
6
1 1 2 3 3 4
6
1 2 1 4 5 4

Sample Outputs:
2
1
2
0

Solution (Python):
import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    p = []
    for i in range(n - 1):
        if a[i] == a[i + 1]:
            p.append(i)
    if len(p) <= 1:
        print(0)
    elif p[-1] - p[0] == 1:
        print(1)
    else:
        print(p[-1] - p[0] - 1)

Solution (Python):
import sys
import copy
import heapq
import bisect
import functools
from math import *
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import groupby
import itertools
from itertools import accumulate
from decimal import Decimal, ROUND_HALF_UP
readline = lambda : sys.stdin.readline().rstrip()

def solve():
    n = int(readline())
    a = list(map(int, readline().split()))
    (l, r) = (-1, -1)
    for i in range(1, n):
        if a[i - 1] == a[i]:
            if l == -1:
                l = i
            r = i
    if l == r:
        print(0)
    else:
        print(max(1, r - l - 1))

def main():
    t = 1
    t = int(readline())
    for i in range(t):
        solve()
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    p = []
    for i in range(n - 1):
        if a[i] == a[i + 1]:
            p.append(i)
    if len(p) <= 1:
        print(0)
    elif p[-1] - p[0] == 1:
        print(1)
    else:
        print(p[-1] - p[0] - 1)