[CSES] Apple Division

1 minute read
Algorithm

Number Spiral

Task:

There are $n$ apples with known weights. Your task is to divide the apples into two groups so that the difference between the weights of the groups is minimal.

Input

The first input line has an integer $n$: the number of apples.

The next line has $n$ integers $p_1,p_2,\dots,p_n$: the weight of each apple.

Output

Print one integer: the minimum difference between the weights of the groups.

Constraints

  • $1 \le n \le 20$
  • $1 \le p_i \le 10^9$
Example

Input:
5
3 2 7 4 1

Output:
1

Explanation: Group 1 has weights 2, 3 and 4 (total weight 9), and group 2 has weights 1 and 7 (total weight 8).

Solutions:

Intuition:

Reducing the gap between 2 piles as fast as possible is the proper way. Because with each move, the gap reduces 1 unit and the valid state is when both piles contain $0$ coin. Hence, $x$ falls into 3 cases: ($x$ is the value of 2 piles when its value is same ).

  • $x=0$ $=>YES$
  • $x>0$: Because, it's equal, we need to do removing interchangeably until reaching $0$. That means we take out 3 coins for each move from 2 piles.
    • If x % 3 == 0 $=>YES$
    • Otherwise, $=>NO$
  • $x<0$ $=>NO$
How can we find x?. As mentioned, each move reduces 1 unit in the gap between them. Hence, the number of necessary move equals the gap, that's gonna make 2 piles have x coins after doing these amounts move.

Implementation:

 1def recur(start,weight,total,cur,track):
 2   res=abs(total-cur*2)
 3   if start>=len(weight):
 4       return res
 5   for i in range(start,len(weight)):
 6       res=min(res,recur(i+1,weight,total,cur+weight[i],track))
 7   return res
 8
 9def solve(n,weight):
10   track=[False]*n
11   return recur(0,weight,sum(weight),0,track)
12       
13if __name__=="__main__":
14   n=int(input().strip())
15   weight=list(map(int,input().strip().split(" ")))
16   print(solve(n,weight))
17

Analysis:

Time complexity: O(1).

Space complexity: O(1).

Help me water it