# 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: introductory

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