Burenka and Traditions (easy version) (Codeforces 1718A1)
Tags: Greedy, dp

This is the easy version of this problem. The difference between easy and hard versions is only the constraints on $$$a_i$$$ and on $$$n$$$. You can make hacks only if both versions of the problem are solved.Burenka is the crown princess of Buryatia, and soon she will become the $$$n$$$-th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $$$n$$$-th ruler, the inhabitants of the country give them an array of $$$a$$$ of exactly $$$n$$$ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times:   select two indices $$$l$$$ and $$$r$$$, so that $$$1 \le l \le r \le n$$$ and a non-negative integer $$$x$$$, then  for all $$$l \leq i \leq r$$$ assign $$$a_i := a_i \oplus x$$$, where $$$\oplus$$$ denotes the bitwise XOR operation. It takes $$$\left\lceil \frac{r-l+1}{2} \right\rceil$$$ seconds to do this operation, where $$$\lceil y \rceil$$$ denotes $$$y$$$ rounded up to the nearest integer. Help Burenka calculate how much time she will need.

Input: The first line contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the size of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — elements of the array. It is guaranteed that the sum of $$$n$$$ in all tests does not exceed $$$5000$$$.

Output: For each test case, output a single number  — the minimum time that Burenka will need.

Note: In the first test case, Burenka can choose segment $$$l = 1$$$, $$$r = 4$$$, and $$$x=5$$$. so it will fill the array with zeros in $$$2$$$ seconds.In the second test case, Burenka first selects segment $$$l = 1$$$, $$$r = 2$$$, and $$$x = 1$$$, after which $$$a = [0, 2, 2]$$$, and then the segment $$$l = 2$$$, $$$r = 3$$$, and $$$x=2$$$, which fills the array with zeros. In total, Burenka will spend $$$2$$$ seconds.

Sample Inputs:
7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55

Sample Outputs:
2
2
0
2
4
7
4

Solution (Python):
T = int(input())
for _ in range(T):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    f = [0] * (n + 1)
    mp = {0: 0}
    sum_val = 0
    for i in range(1, n + 1):
        f[i] = f[i - 1] + 1
        sum_val ^= a[i]
        if sum_val in mp:
            f[i] = min(f[i], f[mp[sum_val]] + i - mp[sum_val] - 1)
        mp[sum_val] = i
    print(f[n])

Solution (Python):
t = int(input())
for i in range(t):
    n = int(input())
    lst = list(map(int, input().split()))
    res = n
    for i in range(1, n):
        lst[i] ^= lst[i - 1]
    st = set()
    st.add(0)
    for i in lst:
        if i in st:
            res -= 1
            st.clear()
        st.add(i)
    print(res)

Solution (Python):
for _ in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    for x in range(1, len(l)):
        l[x] = l[x] ^ l[x - 1]
    res = n
    s = set()
    s.add(0)
    for x in l:
        if x in s:
            res -= 1
            s = set()
        s.add(x)
    print(res)