An arcade redemption counter lets a player turn in ticket stubs for prizes, but only if every stub in the turned-in pile comes from one of at most two point-value tiers, and those two tiers must be exactly 1 point apart (for example, tiers worth 4 and 5, but not tiers worth 4 and 6, and not a single tier alone). Given the point values printed on a roll of n ticket stubs, find the largest possible pile of stubs (choosing any subset of the stubs, not necessarily consecutive on the roll) that uses stubs from exactly two point-value tiers whose values differ by exactly 1.
n, the number of ticket stubs.n space-separated integers, the point value printed on each stub, in the order they were torn from the roll.Print a single integer: the maximum number of stubs in a pile that uses stubs from exactly two distinct point-value tiers differing by exactly 1. If no two stubs have point values differing by exactly 1, print 0.
Example 1
Input
8 1 3 2 2 5 2 3 7
Expected
5
Explanation
There are three stubs worth 2 points and two stubs worth 3 points; 2 and 3 differ by exactly 1, and combining all of them gives a pile of 3 + 2 = 5 stubs, which is the largest such pile available among any adjacent pair of tiers.
Example 2
Input
5 1 1 1 1 1
Expected
0
Explanation
Every stub is worth exactly 1 point, so there is no second tier exactly 1 point away to pair with it; the answer is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →