Make Equal Again (Codeforces 1931C)
Tags: Greedy, brute force

You have an array $$$a$$$ of $$$n$$$ integers. You can no more than once apply the following operation: select three integers $$$i$$$, $$$j$$$, $$$x$$$ ($$$1 \le i \le j \le n$$$) and assign all elements of the array with indexes from $$$i$$$ to $$$j$$$ the value $$$x$$$. The price of this operation depends on the selected indices and is equal to $$$(j - i + 1)$$$ burles. For example, the array is equal to $$$[1, 2, 3, 4, 5, 1]$$$. If we choose $$$i = 2, j = 4, x = 8$$$, then after applying this operation, the array will be equal to $$$[1, 8, 8, 8, 5, 1]$$$.What is the least amount of burles you need to spend to make all the elements of the array equal?

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of input test cases. The descriptions of the test cases follow.The first line of the description of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10 ^ 5$$$) — the size of the array.The second line of the description of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — array elements.It is guaranteed that the sum of $$$n$$$ for all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output one integer — the minimum number of burles that will have to be spent to make all the elements of the array equal. It can be shown that this can always be done.


Sample Inputs:
8
6
1 2 3 4 5 1
7
1 1 1 1 1 1 1
8
8 8 8 1 2 8 8 8
1
1
2
1 2
3
1 2 3
7
4 3 2 7 1 1 3
9
9 9 2 9 2 5 5 5 3

Sample Outputs:
4
0
2
0
1
2
6
7

Solution (Python):
tests = int(input())
for t in range(tests):
    size = int(input())
    array = input().split(' ')
    if size == 1:
        print(0)
        continue
    burles1 = size
    burles2 = size
    burles3 = size
    num1 = array[0]
    last = 0
    for _ in range(0, size):
        if array[_] == num1:
            burles1 = burles1 - 1
            last = _
        else:
            break
    num2 = array[-1]
    for _ in range(size - 1, last, -1):
        if array[_] == num2:
            burles2 = burles2 - 1
        else:
            break
    if array[0] == array[-1]:
        burles3 = burles1 - size + burles2
    print(min(burles1, burles2, burles3))

Solution (Python):
t = int(input())
ns = []
ps = []
for z in range(t):
    ns.append(int(input()))
    ps.append(input().split())
for (n, p) in zip(ns, ps):
    (fs, ls) = (1, 1)
    for i in range(1, n):
        if p[i] == p[0]:
            fs += 1
            continue
        break
    if fs == n:
        print(0)
        continue
    for i in range(n - 2, -1, -1):
        if p[i] == p[-1]:
            ls += 1
            continue
        break
    if p[0] == p[-1]:
        print(n - (fs + ls))
        continue
    print(n - max(ls, fs))

Solution (Python):
import sys

def get_cost(a, n, stdval):
    start = n - 1
    for i in range(n):
        if stdval != a[i]:
            start = i
            break
    end = n - 1
    for j in range(n - 1, -1, -1):
        if stdval != a[j]:
            end = j
            break
    return max(end - start + 1, 0)

def main():
    n = int(sys.stdin.readline())
    (*a,) = map(int, sys.stdin.readline().split())
    sameAll = True
    for ai in a:
        if ai != a[0]:
            sameAll = False
            break
    if sameAll:
        print(0)
        return
    val1 = get_cost(a, n, a[0])
    val2 = get_cost(a, n, a[-1])
    print(min(val1, val2))
    return
T = int(sys.stdin.readline())
for _ in range(T):
    main()