# Fine the smallest difference between elements in an array, given a restricted numbers of element to choose from the array

I have a C++ algorithm problem:

1. an array num_list[n] with n < 200000
2. a number s which indicates the number of items in array to pick out.
3. a requirement that those items have the largest intervals between themselves.
4. output: the items of the array that should be picked out.

For example: with num_list[6] = { 1, 10, 11, 12, 99, 100 } and s = 3, I would pick 1, 12, 100 because the interval between them are 11, and 88 would be the largest possible.

My approach:

1. Step 1: sorted out the array num_list[] in ascending order.
2. Step 2: make an array choice[] to store possible items in array num_list , assign choice[0] = num_list[0]
3. Step 3: run an outer loop from i->s,
run an inner loop from j-> size of num_list[],
find the next possible item in num_list[] to put into choice[i]

The “sub-problem” that I stumble is step 3: find the next possible item in A to put into X[i].

Intuitively, I would do

1. choice[0] = i ; // push the first item
2. choice[s-1] = num_list[n-1] // push the last item (can’t do it with vector)
3. next numlist[i] = num_list[j]* where A[j]* or j* is within a “range”. For example:
``````num_list[7] = {1, 9, 10, 11, 12, 90, 100}
s  = 4
Step 1: choice[0] = 1, choice[3] = 100;
Step 2: run a looping process and choice[2] = 90, choice[3] = 12
``````

I run a kind of “binary search” for step 3 and it doesn’t work yet. On some trials, I would get choice[3] = 9. The code below returns infinitive loop.

Could some one help this poor dummy dude ?

``````#include<iostream>
#include<vector>
#include <algorithm>
#include <cmath>

using namespace std;

int binary_search(int &low, int &high, vector<int> num_list){
cout<<"--binary_search"<<endl;
for (int j = 0; j< 6; j++ ){
if (num_list[j]> low){
cout<<"num_list[j]: "<<num_list[j]<<endl;
return num_list[j];
}
else{
high = low;
int new_low = (high + low)/2;
binary_search(new_low, high, num_list);
}
}
}

// run result for all test cases
void printResult(vector<int>Result){
cout<<"Result: "<<endl;
for (int i : Result){
cout<<i<<" "<<endl;
}
}

// for each T, run a Test Case, accept inputs
void runTestCase(){
// declare inputs as required by problem.
int n, s;           //n is the size of num_list
//s is the size of choice
cin >> n >> s;

// vector<int> num_list;
vector<int>num_list;

for (int i = 0; i < n; i++)
{
int num;
cin >> num;
num_list.push_back(num);
}

sort(num_list.rbegin(), num_list.rend(), greater<int>());
// log: test output
cout <<"sorted num_list[i]: "<<endl;
for (int i = 0; i < n; i++)
{
cout << num_list[i] <<" ";
}
cout<<endl;

// solving problem:
vector<int> choice;
// Step 1:
auto iterator = choice.begin();
choice.insert(iterator, num_list[0]);                  // choice[0]
// choice.insert(iterator + s-1, num_list[n-1]);       // choice[s-1] can't really do with vector.

// Step 2:
// for (int i = 0 ; i < s; i++)                        // since num_list is a vector, do not use for loop
{
int mid = num_list[(n-1)] - num_list[0];
choice.push_back(binary_search(mid, num_list[(n-1)], num_list));
}

printResult(choice);
}

// Solution
void TestCase(int testCase[10], int totalTestCase){
// run test case
for (int i =0; i < totalTestCase; i++ )    {
runTestCase();
}
}

int main(){
int T;
cin>>T;
int testCase [10];
TestCase(testCase, T);
return 0;
}
``````