# 1674. Minimum Moves to Make Array Complementary

- Given n couples
- Every person has some number of candy in hand.
- Given an positive integer M, everyone can change the number of candy in hand to some value in [1, M].
- Return the minimum number of changes such that all couples have "the same number of candies".

M = 4
couple 0: [1, 3]
couple 1: [2, 4]
answer = 1, 1 + 3 = 2 + (4->2)

M = 4
couple 0: [1, 3]
couple 1: [4, 4]
answer = 2, 1 + 3 = (4->1) + (4->3)

    M = 10
   [1,1], [2,2], [9,9], [10,10]
   
   // optimal 4
   // fixed 1 couple -> 6
   
   M = 10
   [3,5] ->8
   range    [2,3] [4,7]  8  [9,15] [16,20]
   changes    2     1    0    1         2
   
   
   
   c1=7 c2=7 c3=9  [2, 2M]
   
   sol 1:
   c1 [1, 2]  -> c2[4->1, 4->2] +2, c3c2[1, 4->2] -> 3
   c2 [4, 4]  -> c1+1, c3+2 -> 3
   
   
   sol2
   
   [3, 5] -> [2, M]
   dp[2...M] = [22221111011112222] -> c1
             = [22221111011111122] -> c2
             
   O(NM)
   loop (c N)
       loop (dp M)
   

# M = 10, [3,5]
# range    [2,3] [4,7]  8  [9,15] [16,20]
# changes    2     1    0    1       2
def findCouple(couples, M):
    
    # [2,3] -> [10, 3]=13 or [2, 10]=12 -> max=13
    def getUpperBound(c1, c2):
        poss1 = M + c2
        poss2 = c1 + M
        return max(poss1, poss2)
    
    # [2,3] -> [1, 3]=4 or [2, 1]=3 -> min=3
    def getLowerBound(c1, c2):
        poss1 = 1 + c2
        poss2 = c1 + 1
        return min(poss1, poss2)
    
    # step1 init
    dp = [0]*(2*M+2) # padding
    
    # step2 loop couple O(NM)
    for c1, c2 in couples:
        sumOfC1C2 = c1 + c2
        # [2,3] -> [10, 3]=13 or [2, 10]=12 -> max=13
        upperBound = getUpperBound(c1, c2)
        
        # [2,3] -> [1, 3]=4 or [2, 1]=3 -> min=3
        lowerBound = getLowerBound(c1, c2)
        
        dp[2] += 2
        dp[lowerBound] -= 1
        dp[sumOfC1C2] -= 1
        dp[sumOfC1C2+1] += 1
        dp[upperBound+1] += 1
        # [22221111011111122]
        """for i in range(1, len(dp)):
            if sumOfC1C2 == i:
                continue
            elif i < lowerBound or i > upperBound:
                dp[i] += 2
            else
                dp[i] += 1"""
    
    ans = inf
    pre = 0
    for n in dp[:2M+1]:
        pre += n
        ans = min(ans, pre)
    
    return ans
            
    
    # step3
    

[2 1 1 0 1 1 2 ] ->
[2 -1 0 -1 1 0 1 ]
0 l X i i+1 X u+1

2. 1. 1. 0. 1. 1. 2