# Picking Numbers - HackerRank | C++ Implementation

# Problem:

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.

For example, if your array is a = [1, 1, 2, 2, 4, 4, 5, 5, 5], you can create two subarrays meeting the criterion: [1, 1, 2, 2] and [4, 4, 5, 5, 5]. The maximum length subarray has 5 elements.

Read the full problem here: Picking Numbers

# Solution:

To find the subarrays which satisfy the above conditions, the input array must be sorted. So our first statement in the function is

1

std::sort(array.begin(), array.end());

Integer variable `result`

will store the length of the subarray with maximum size, `count`

will store the length of the subarray being processed and `subarray_first_element`

will store the first element of the subarray being processed.

`result`

is initialised with `0`

, `subarray_first_element`

with the first element of the array and `count`

with `1`

.

1
2
3

int result = 0;
int count = 1;
int subarray_first_element = array[0];

`count`

is initialised with `1`

because we iterate from the index 1 of the array. The element being considered is checked with `subarray_first_element`

and if the condition is `true`

, `count`

is incremented and we have two elements in the subarray.

If the condition is `false`

, `result`

is updated if the `count`

is greater than the `result`

(or length of this subarray is greater than the previous subarray). `count`

is initialised with `1`

and `subarray_first_element`

with `array[i]`

.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

for (int i = 1; i < array.size(); ++i)
{
if (subarray_first_element == array[i] || subarray_first_element + 1 == array[i])
{
count++;
}
else
{
if (count > result)
{
result = count;
}
count = 1;
subarray_first_element = array[i];
}
}

Once the loop is executed again we check if the `count`

is greater than the `result`

, because if the last two elements of the array satisfies the above conditions then the control did not enter in the else scope in the for loop and `result`

is not updated with the correct `count`

.

1
2
3
4
5

if (count > result)
{
result = count;
}
return result;

### C++ Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#include <iostream>
#include <algorithm>
#include <vector>
int picking_numbers(std::vector<int>& array)
{
std::sort(array.begin(), array.end());
int result = 0;
int count = 1;
int subarray_first_element = array[0];
for (int i = 1; i < array.size(); ++i)
{
if (subarray_first_element == array[i] || subarray_first_element + 1 == array[i])
{
count++;
}
else
{
if (count > result)
{
result = count;
}
count = 1;
subarray_first_element = array[i];
}
}
if (count > result)
{
result = count;
}
return result;
}
int main()
{
int size_of_array;
std::cin >> size_of_array;
std::vector<int> array(size_of_array);
for (int i = 0; i < size_of_array; ++i)
{
std::cin >> array[i];
}
int max_count = picking_numbers(array);
std::cout << max_count << "\n";
}

View this on Github

If you have another solution then please share it in the comments below.

### Other Competitive Programming Problems and Solutions