Question: Makemytrip, Online Assessment Question (NIT Jamshedpur ; 6M Internship ) | Maximum Separation | Telephone Connections | 15th September 2023
0
Entering edit mode

Entering edit mode
0
First question can be done using binary search

 

 

ADD REPLYlink 7 months ago
waitforit
• 0
0
Entering edit mode

Answer for Maximum Sepration Problem:
 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool isPossible(vector<int>& position, int M, int distance) {
    int count = 1;
    int prev = position[0];
    
    for (int i = 1; i < position.size(); i++) {
        if (position[i] - prev >= distance) {
            count++;
            prev = position[i];
        }
    }
    
    return count >= M;
}

int solve(int N, int M, vector<int>& position) {
    sort(position.begin(), position.end());
    
    int left = 1;
    int right = position[N-1] - position[0];
    int result = 0;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
   

int main() {
    int N, M;
    cin >> N >> M;
    
    vector<int> position(N);
    for (int i = 0; i < N; i++) {
        cin >> position[i];
    }
    
    int answer = solve(N, M, position);
    cout << answer << endl;
    
    return 0;
}

ode snippet widgetcode snippet widget

ADD COMMENTlink 7 months ago waitforit • 0

Login before adding your answer.

Similar Posts
Loading Similar Posts