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

Library Fine
Sherlock and Squares