21 months ago

RITU RAJ PRASAD • 30

Warangal

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to check if it is feasible to have a distance `dist` between chosen integers
bool is_feasible(const vector<int>& starts, int d, int n, int dist) {
    int current = starts[0];
    
    for (int i = 1; i < n; ++i) {
        int next_start = current + dist;
        
        // Check if there is a valid number in the next range
        if (next_start > starts[i] + d) {
            return false;
        }
        
        // Update the current chosen number to the valid next_start
        current = max(next_start, starts[i]);
    }
    
    return true;
}

// Function to find the maximum possible value of `dist`
int max_dist(vector<int>& starts, int d) {
    int n = starts.size();
    
    // Sort the starts array
    sort(starts.begin(), starts.end());
    
    // Initialize binary search bounds
    int low = 0, high = *max_element(starts.begin(), starts.end()) + d - *min_element(starts.begin(), starts.end());
    
    // Binary search to find the maximum dist
    while (low < high) {
        int mid = (low + high + 1) / 2;
        if (is_feasible(starts, d, n, mid)) {
            low = mid;
        } else {
            high = mid - 1;
        }
    }
    
    return low;
}

// Main function
int main() {
    int n = 3;
    int d = 2;
    vector<int> starts = {3, 2, 3};
    
    cout << max_dist(starts, d) << endl;  // Output: 1

    return 0;
}
 

2.2 years ago

unicornme707 • 20

Mumbai

1.) Sort the Range Query & Binary Search over max(Range[i] + d). For each check the feasibility which can be checked in O(N).

2.) Create a graph, adjacency list and for each i, perform the operations. 

2.6 years ago

Parth Chaturvedi • 0

What are the constraints for Q1 - Transferrable Weights