# Picking Numbers

Picking Numbers: This is an algorithm implementation problem that can be featured in any coding interview round. Submitted by Radib Kar, on March 08, 2019

## Problem statement

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
```

## Explanation with example

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)

```FUNCTION pickingNumbers(input array)
1.  Declare   map<int,int>m to store key with their frequencies;
2.  Build the map.
For  i=0:length of array
m[array[i]]++;
3.  Declare max as INT_MIN;
4.  Declare map<int,int>::iteratorit;
5.  For(it=m.begin();it!=m.end();it++)
IF (it+1==m.end()) //last case
IF(it->second>max)
max=it->second;
END IF
ELSE IF(it->first+1==(it+1)->first){ //absolute difference is 1
IF((it->second +(it+1)->second)>max)
max=it->second +(it+1)->second;
END IF
ELSE
IF(it->second>max) //absolute difference 0 case
max=it->second;
END IF
END IF-ELSE
END FOR

6.  return max;
END FUNCTION
```

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.

```    The input array is: 6, 4, 6, 8, 5, 9, 9, 9, 10, 3
Map m:
Key 			Frequency
3				1
4				1
5				1
6				2
8				1
9				3
10				1

So if we do all the iterations then each iteration,
maxgets to be updated(or not, keeps last value)
From this map, we can see max is 4
1+3 //one 8 and three 9
3+1 //three 9 and one 10
Now lets think that we append six 12 to the array
Thus input is now: 6, 4, 6, 8, 5, 9, 9, 9, 10, 3, 12, 12, 12, 12, 12, 12
Map m:
Key 			Frequency
3				1
4				1
5				1
6				2
8				1
9				3
10				1
12				6
Now the max will be 6 //absolute difference 0 case
Since the subset will be {12, 12, 12, 12, 12, 12}
```

## C++ Implementation

```#include <bits/stdc++.h>
using namespace std;

int pickingNumbers(vector<int> a)
{
map<int,int> m;
for(int i=0;i<a.size();i++)
m[a[i]]++;

int max=INT_MIN;
map<int,int>::iterator it;
for(it=m.begin();it!=m.end();it++){
//std::next(it) points to it+1
if((std::next(it))==m.end()){
if(it->second>max)
max=it->second;
}
else if(it->first+1==(std::next(it))->first){
if((it->second +(std::next(it))->second)>max)
max=it->second +(std::next(it))->second;
}
else{
if(it->second>max)
max=it->second;
}
}

return max;
}

int main(){
int n,item;

cout<<"Enter number of elements in the array\n";
cin>>n;

vector<int> a;
cout<<"enter numbers\n";
for(int i=0;i<n;i++){
cin>>item;
a.push_back(item);
}
cout<<"Maximum no of such numbers can be picked: "<<pickingNumbers(a)<<endl;

return 0;
}
```

Output

```First run:
Enter number of elements in the array
10
enter numbers
6 4 6 8 5 9 9 9 10 3
Maximum no of such numbers can be picked: 4

Second run:
Enter number of elements in the array
16
enter numbers
6 4 6 8 5 9 9 9 10 3 12 12 12 12 12 12
Maximum no of such numbers can be picked: 6
```
The text passage describes a coding problem and provides an algorithm, examples, and a C++ implementation to solve it. The problem is to find the maximum number of integers that can be selected from an array such that the absolute difference between any two chosen integers is less than or equal to 1.
no_question

the passage does not contain a direct mathematical question or a word problem that requires a solution. instead, it provides a problem statement, an algorithm, and examples to illustrate the solution. the examples and the c++ code demonstrate the solution to the problem, but they do not pose a question that needs to be answered separately.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Picking Numbers

Picking Numbers: This is an algorithm implementation problem that can be featured in any coding interview round. Submitted by Radib Kar, on March 08, 2019

## Problem statement

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
```

## Explanation with example

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)

```FUNCTION pickingNumbers(input array)
1.  Declare   map<int,int>m to store key with their frequencies;
2.  Build the map.
For  i=0:length of array
m[array[i]]++;
3.  Declare max as INT_MIN;
4.  Declare map<int,int>::iteratorit;
5.  For(it=m.begin();it!=m.end();it++)
IF (it+1==m.end()) //last case
IF(it->second>max)
max=it->second;
END IF
ELSE IF(it->first+1==(it+1)->first){ //absolute difference is 1
IF((it->second +(it+1)->second)>max)
max=it->second +(it+1)->second;
END IF
ELSE
IF(it->second>max) //absolute difference 0 case
max=it->second;
END IF
END IF-ELSE
END FOR

6.  return max;
END FUNCTION
```

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.

```    The input array is: 6, 4, 6, 8, 5, 9, 9, 9, 10, 3
Map m:
Key 			Frequency
3				1
4				1
5				1
6				2
8				1
9				3
10				1

So if we do all the iterations then each iteration,
maxgets to be updated(or not, keeps last value)
From this map, we can see max is 4
1+3 //one 8 and three 9
3+1 //three 9 and one 10
Now lets think that we append six 12 to the array
Thus input is now: 6, 4, 6, 8, 5, 9, 9, 9, 10, 3, 12, 12, 12, 12, 12, 12
Map m:
Key 			Frequency
3				1
4				1
5				1
6				2
8				1
9				3
10				1
12				6
Now the max will be 6 //absolute difference 0 case
Since the subset will be {12, 12, 12, 12, 12, 12}
```

## C++ Implementation

```#include <bits/stdc++.h>
using namespace std;

int pickingNumbers(vector<int> a)
{
map<int,int> m;
for(int i=0;i<a.size();i++)
m[a[i]]++;

int max=INT_MIN;
map<int,int>::iterator it;
for(it=m.begin();it!=m.end();it++){
//std::next(it) points to it+1
if((std::next(it))==m.end()){
if(it->second>max)
max=it->second;
}
else if(it->first+1==(std::next(it))->first){
if((it->second +(std::next(it))->second)>max)
max=it->second +(std::next(it))->second;
}
else{
if(it->second>max)
max=it->second;
}
}

return max;
}

int main(){
int n,item;

cout<<"Enter number of elements in the array\n";
cin>>n;

vector<int> a;
cout<<"enter numbers\n";
for(int i=0;i<n;i++){
cin>>item;
a.push_back(item);
}
cout<<"Maximum no of such numbers can be picked: "<<pickingNumbers(a)<<endl;

return 0;
}
```

Output

```First run:
Enter number of elements in the array
10
enter numbers
6 4 6 8 5 9 9 9 10 3
Maximum no of such numbers can be picked: 4

Second run:
Enter number of elements in the array
16
enter numbers
6 4 6 8 5 9 9 9 10 3 12 12 12 12 12 12
Maximum no of such numbers can be picked: 6
```
user
The text passage describes a coding problem and provides an algorithm, examples, and a C++ implementation to solve it. The problem is to find the maximum number of integers that can be selected from an array such that the absolute difference between any two chosen integers is less than or equal to 1.

TYPE: NO_QUESTION

The passage does not contain a direct mathematical question or a word problem that requires a solution. Instead, it provides a problem statement, an algorithm, and examples to illustrate the solution. The examples and the C++ code demonstrate the solution to the problem, but they do not pose a question that needs to be answered separately.