in

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;
}



Source: https://stackoverflow.com/questions/70720947/fine-the-smallest-difference-between-elements-in-an-array-given-a-restricted-nu

DoT Looks to Accelerate the Process of Installing Mobile Towers at Airports

Reslant — Collect feedback, assist users, share updates with a forum