Given an array of integers, find and print the maximum number of integers you can select from the array such that the absolute difference between any two of the chosen integers is less than or equal to 1.
Examples:
Input array:
6, 4, 6, 8, 5, 9, 9, 9, 10, 3
Output:
4
Example with explanation:
The input array is: 6, 4, 6, 8, 5, 9, 9, 9, 10, 3
No we can pick up different sets for which the absolute difference between any two numbers in the set is 1.
Possible sets are:
{6, 6, 5}
{4, 5}
{8, 9, 9, 9}
{9, 9, 9, 10}
{4, 3}
Thus maximum no of picked up elements is: 4
Algorithm:
This problem can be implemented with help of map data structure. We have used STL for map implementation. (For details regarding STL map, C++ STL Map)
Algorithm is pretty simple.
We first extract the unique numbers and store their frequencies. Then we simply check for two unique number's additive frequency or any one unique number's frequency itself and return the greater one.
Let's solve the above example.
C++ implementation:
Output