Deck of Cards

In a deck of cards, each card has an integer written on it.

Return 1 if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, else return 0 where:

• Each group has exactly X cards.
• All the cards in each group have the same integer.

Input Format

First parameter - number n.

Second parameter - array arr of size n.

Output Format

Return a number

Example 1:

Input: 8
       1 2 3 4 4 3 2 1
Output: 1
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4].

Example 2:

Input: 8
       1 1 1 2 2 2 3 3
Output: 0
Explanation: No possible partition.

Constraints:

• 1 <= n <= 10^4
• 0 <= arr[i] < 10^4
• Expected Time Complexity: O(n log n)
• Expected Space Complexity: O(n)