Coins

2.8

14 votes
Algorithms, Binary Search, Easy, Searching, Two pointer
Problem

There are N bags and each bag contains some coin(s). Your task is to select an integer X and remove all the bags in which the number of coins is equal to X. Divide the remaining bags into two non-empty groups such that:

  1.  The number of coin(s) in each bag of the first group is strictly smaller than X.
  2. The number of coin(s) in each bag of the second group is strictly larger than X.
  3. The total number of coins of one group is equal to the other.

Input Format:

The first line contains an integer N(1N105) denoting the number of bags.
The second line contains N space-separated integers, denoting the number of coins in N bags. The ith integer denotes the values of Ai(1Ai105).

Output Format:

Print YES, if it is possible to divide the bags into two groups, else print NO.

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

We can choose X as 3,then there are 3 bags which has less than 3 coins therefore their sum is 1+1+2=4.And there is only one bag with number of coins greater than 3 and their sum is 4. Since value of both sums are equal, the answer is "YES".

Editor Image

?