1788A - One and Two - 800

1788A - One and Two (brute force, implementation, math, 800)

This problem is about finding a specific index 𝑘 in a given sequence of integers $𝑎_1,𝑎_2,…,𝑎_𝑛$, where each element is either 1 or 2. The goal is to determine whether there exists an integer 𝑘 such that the product of all elements from $𝑎_1$ to $𝑎_𝑘$ is equal to the product of all elements from $𝑎_𝑘+1$ to $𝑎_𝑛$.

Because of product of 1 doesn’t change the result we can focus on 2. Product in left side and in the right side can be equal only if count of 2 is even or equal 0.

1. We can count number of 2.
2. The result will be the index of the middle 2 in array.

Solution

def solve(ar):
    twos = ar.count(2)
    if twos % 2 != 0:
        return -1

    passed_twos = 0
    need_twos = twos // 2
    for i, x in enumerate(ar):
        if x == 2:
            passed_twos += 1
        if passed_twos == need_twos:
            return i+1

t = int(input())
for _ in range(t):
    n = int(input())
    ar = list(map(int, input().split()))
    print(solve(ar))