# Task

You are given an array `a` of positive integers a. You may choose some integer `X` and update `a` several times, where to update means to perform the following operations:
```
pick a contiguous subarray of length not greater than the given k;
replace all elements in the picked subarray with the chosen X.
```
What is the minimum number of updates required to make all the elements of the array the same?

# Example

For `a = [1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 1] and k = 2`, the output should be `4`.

Here's how a will look like after each update:
```
[1, 2, 2, 1, 2, 1, 2, 2, 2, 1, 1, 1] ->
[1, 1, 1, 1, 2, 1, 2, 2, 2, 1, 1, 1] ->
[1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1] ->
[1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1] ->
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
```


# Input/Output


 - `[input]` integer array `a`

  An array of positive integers.

  Constraints:
  
  `10 ≤ a.length ≤ 50,`
  
  `1 ≤ a[i] ≤ 10.`
  

 - `[input]` integer `k`

  A positive integer, the maximum length of a subarray.

  Constraints: `2 ≤ k ≤ 9.`


 - `[output]` an integer

  The minimum number of updates.

Difficulty: EASY
Tags: Ad-hoc

Starter code:
def array_equalization(a, k):
	

Solutions:
def array_equalization(a, k):
	(totals, ends) = ({}, {})
	for (i, n) in enumerate(a):
		if n not in ends:
			(totals[n], ends[n]) = (0, -1)
		if i < ends[n]:
			continue
		count = (i - ends[n] - 1 + k - 1) // k
		totals[n] += count
		ends[n] = max(i, ends[n] + count * k)
	return min((t + (len(a) - ends[n] - 1 + k - 1) // k for (n, t) in totals.items() if ends[n] < len(a)))


def array_equalization(a, k):
	keys = set(a)
	ans = []
	for x in keys:
		i = 0
		c = 0
		while i < len(a):
			if a[i] == x:
				i += 1
			else:
				c += 1
				i += k
		ans.append(c)
	return min(ans)


def array_equalization(a, n):
	(MIn, l) = ([], len(a))
	for X in a:
		(i, pa, c) = (0, a[:], 0)
		while i < len(pa):
			if pa[i] != X:
				pa[i:i + n] = [X] * min(n, l)
				c += 1
			i += 1
		MIn.append(c)
	return min(MIn)


def array_equalization(a, k):
	sum = {}
	for (i, n) in enumerate(a):
		arr = sum.get(n)
		if not arr:
			sum[n] = [i]
		else:
			sum[n].append(i)
	print(list(sum.values()))
	times_arr = []
	for arr in list(sum.values()):
		i = 0
		pos = 0
		times = 0
		while 1:
			if i >= len(arr) or pos < arr[i]:
				pos += k
				times += 1
			elif pos == arr[i]:
				pos += 1
				i += 1
			else:
				i += 1
			if pos >= len(a):
				break
		times_arr.append(times)
	return min(times_arr)


def array_equalization(a, k):
	min_ = float('inf')
	for x in set(a):
		count = 0
		i = 0
		while i < len(a):
			if a[i] != x:
				count += 1
				i += k
			else:
				i += 1
		min_ = min(count, min_)
	return min_


def array_equalization(a, k):
	(n, r) = (len(a), len(a))
	for x in set(a):
		(i, t) = (0, 0)
		while i < n:
			if a[i] != x:
				t += 1
				i += k
			else:
				i += 1
		r = min(r, t)
	return r


def array_equalization(a, k):
	counter = 0
	arr = []
	m = 0
	print(a, k)
	for x in range(11):
		m = x
		lst = a.copy()
		counter = 0
		for i in range(len(lst)):
			if lst[i] != m and i + k <= len(lst):
				counter += 1
				for j in range(i, i + k):
					if lst[j] != m:
						lst[j] = m
			elif lst[i] != m and i + k > len(lst):
				counter += 1
				for j in range(i, len(lst)):
					if lst[j] != m:
						lst[j] = m
		arr.append(counter)
	return min(arr)


def array_equalization(a, k):
	l_a = len(a)
	if k >= l_a - 1:
		return 1
	sa = set(a)
	times_list = []
	for i in sa:
		templs = []
		times = 0
		for j in range(0, l_a):
			if j > 0 and j == len(templs) or j == 0:
				if a[j] == i:
					templs.append(i)
				else:
					templs += [i] * k
					times += 1
		times_list.append([times])
	return min(times_list)[0]


def array_equalization(a, k):
	m = n = len(a)
	for number in set(a):
		c = 0
		i = 0
		while i < n:
			if a[i] != number:
				c += 1
				i += k
			else:
				i += 1
		m = min(c, m)
	return m


from collections import Counter

def array_equalization(a, k):
	n = len(a)
	freq = Counter(a)
	m = n
	for number in freq.keys():
		c = 0
		i = 0
		while i < len(a):
			if a[i] != number:
				c += 1
				i += k
			else:
				i += 1
		m = min(c, m)
	return m