# Task
 You are given an array of integers. Your task is to determine the minimum number of its elements that need to be changed so that elements of the array will form an arithmetic progression. Note that if you swap two elements, you're changing both of them, for the purpose of this kata.

 Here an arithmetic progression is defined as a sequence of integers such that the difference between consecutive terms is constant. For example, `6 4 2 0 -2` and `3 3 3 3 3` are arithmetic progressions, but `0 0.5 1 1.5` and `1 -1 1 -1 1` are not.

# Examples

  For `arr = [1, 3, 0, 7, 9]` the answer is `1` 
  
  Because only one element has to be changed in order to create an arithmetic progression.
    
  For `arr = [1, 10, 2, 12, 3, 14, 4, 16, 5]` the answer is `5` 
 
  The array will be changed into `[9, 10, 11, 12, 13, 14, 15, 16, 17]`.

# Input/Output


 - `[input]` integer array `arr`

  An array of N integers.
  
  `2 ≤ arr.length ≤ 100`
  
  `-1000 ≤ arr[i] ≤ 1000`

  Note for Java users: you'll have a batch of 100 bigger random arrays, with lengths as `150 ≤ arr.length ≤ 300`.
  

 - `[output]` an integer

  The minimum number of elements to change.

Difficulty: introductory

Starter code:

def fix_progression(arr):
	

Solutions:
from collections import defaultdict

def fix_progression(arr):
    res = 0
    for i in range(len(arr)):
        D = defaultdict(int)
        for j in range(i):
            q, r = divmod(arr[i]-arr[j], i-j)
            if not r:
                D[q] += 1
                res = max(res, D[q])
    return len(arr)-res-1

from collections import defaultdict
from itertools import combinations


def lineEq(x,a,y,b):
    slope = (b-a)/(y-x)
    ordo  = a - slope * x
    return (slope,ordo), not slope%1


def fix_progression(arr):
    
    c = defaultdict(set)
    for (x,a),(y,b) in combinations(enumerate(arr), 2):
        tup, isIntSlope = lineEq(x,a,y,b)
        if isIntSlope: c[tup] |= {x,y}
    
    return len(arr) - max(map(len, c.values()))

def fix_progression(arr):
    best = len(arr)
    s = sum(arr) / len(arr)
    for start in range(len(arr)-1):
        for idx in range(start+1, len(arr)):
            count = 0
            d = (arr[idx] - arr[start]) // (idx - start)
            for i in range(0, start):
                if arr[i] != arr[start] - d*(start-i):
                    count += 1
            for i in range(start+1, len(arr)):
                if arr[i] != arr[start] + d*(i-start):
                    count += 1
            best = min(best, count)
    return best


def fix_progression(arr):
    n, r = len(arr), float('inf')
    for i in range(n - 1):
        x = arr[i]
        for j in range(i + 1, n):
            d = arr[j] - arr[i]
            if d % (j - i):
                continue
            d //= j - i
            x0 = x - i * d
            diff = sum(arr[k] != x0 + k * d for k in range(n))
            r = min(r, diff)
            if r <= 1:
                return r
    return r

from collections import defaultdict

def fix_progression(arr):
    
    global_max = 1
    
    for i, ele in enumerate(arr):
        
        maxi = 1
        things = defaultdict(lambda: 1) #dictionary to store the first and last elements of progression including arr[i]
        
        for j in range(i+1, len(arr)):
            
            comp = arr[j]
            diff = (comp - ele)/(j-i) #would be arithmetic progression constant between arr[i] and arr[j]
                
            if diff.is_integer():
                
                #calculate the first and last elements of the "would be" arithmetic progression
                
                left = ele - diff*i
                right = ele + diff*(len(arr) - i - 1)
                
                # if the same left and right exist already, that means the current left, right pair is the same
                #as a arithmetic progression seen for arr[i], meaning we have += 1 points sharing the arithmetic progression
                #eg [1, 10, 2, 12, 3, 14]. the pair 10,12 and 10,14 have the same left and right points, meaning they 
                # are collinear and so thats one less point which we need to change in order to make arithmetic prog.
                
                things[(left, right)] += 1 
                maxi = max(maxi, things[(left, right)])
                global_max = max(maxi, global_max)
    
    return len(arr) - global_max


def fix_progression(arr):
  best = len(arr)-2
  for i in range(len(arr)-1):
      for j in range(i+1,len(arr)):
          if (arr[j]-arr[i])%(j-i)!=0:
              continue
          step = (arr[j]-arr[i])//(j-i)
          wrongs = sum(1 for k in range(len(arr)) if arr[k]!=arr[i]+(k-i)*step)
          best = min(wrongs, best)
          if best<i-2:
              break
  return best

def fix_progression(arr):
    min_c=len(arr)
    for i in range(len(arr)-1):
        for j in range(i+1,len(arr)):
            if (arr[j]-arr[i])%(j-i)!=0:
                continue
            a=(arr[j]-arr[i])//(j-i)
            c=0
            for k in range(len(arr)):
               if arr[i]+(k-i)*a!=arr[k]:
                   c+=1
            if c<min_c:
                min_c=c
    return min_c

from itertools import combinations

def fix_progression(arr):
    ans = len(arr) - 1
    for l, r in combinations(range(len(arr)), 2):
        step = (arr[r] - arr[l]) / (r - l)
        if step.is_integer():
            step = int(step)
            changed = sum(a != i for i, a in zip(range(arr[l]-step*l, 10**10*step, step), arr)) if step else sum(a != arr[l] for a in arr)
            ans = min(ans, changed)
    return ans

from collections import Counter
def fix_progression(arr):
    lst = []
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            if (arr[j]-arr[i])%(j-i) == 0:
                dif = (arr[j]-arr[i])//(j-i)
                s = arr[i] - i*dif
                lst.append((s, dif))
    c = Counter(lst).most_common()[0]
    count = 0
    for i in range(len(arr)):
        if arr[i] != c[0][0] + i*c[0][1]:
            count += 1
    return count

from collections import Counter

def fix_progression(arr):
  params = Counter()
  for i in range(len(arr)):
      for j in range(i+1, len(arr)):
          if (arr[j] - arr[i]) % (j - i) == 0:
              d = (arr[j] - arr[i]) // (j - i)
              s = arr[i] - i*d
              params[(s,d)] += 1
              
  start, diff = params.most_common(1)[0][0]
  
  count = 0
  for i in range(len(arr)):
      if arr[i] != start + i * diff:
          count += 1
  return count