We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Hackerland Radio Transmitters
  2. Discussions

Hackerland Radio Transmitters

Sort by

recency

|

43 Discussions

|

  • ny6et8dny6y4
     + 0 comments

    C++ solution O(n)

    int hackerlandRadioTransmitters(vector<int> x, int k) {
    sort(x.begin(),x.end());
    int count=0;
    int lastTransmittersMinCoverRange = INT_MIN;
    int lastTransmittersMaxCoverRange = INT_MIN;
    for(int n:x)
    {
        if (n>lastTransmittersMaxCoverRange)
        {
            count++;
            lastTransmittersMinCoverRange = n;
            lastTransmittersMaxCoverRange = n+k;
        }
        else {
            if(lastTransmittersMinCoverRange>=n-k)
            {
                lastTransmittersMaxCoverRange = n+k;
            }
        }
    }
    return count;
}

  • hs8436686
     + 0 comments

    JavaScript Solution:- function hackerlandRadioTransmitters(x, k) { // Sort the house locations x.sort((a, b) => a - b);

    let i = 0;
let count = 0;
let n = x.length;

while (i < n) {
    count++;
    let loc = x[i] + k; // Find the farthest house that can be covered by a transmitter
    while (i < n && x[i] <= loc) i++; // Move to the farthest house within range

    i--; // Place the transmitter at the farthest house within range
    loc = x[i] + k; // Define the coverage of this transmitter

    while (i < n && x[i] <= loc) i++; // Skip all covered houses
}

return count;

    }

  • kamil_m_antoncz1
     + 0 comments

    Java with single loop

    public static int hackerlandRadioTransmitters(List<Integer> x, int k) {
        int counter = 0;
        int trans = 0;
        int minInRange = 0;
        
        x = x.stream().distinct().sorted().collect(toList());
        for(int n:x){
            if(trans == 0){
                trans = n;
                counter++;
            } else if(inRange(trans, n, k)){
                if (minInRange == 0){
                    minInRange = trans;
                    trans = n;
                } else if (inRange(minInRange, n, k)){
                        trans = n;
                }
            } else {
                trans = n;
                minInRange = 0;
                counter++;
            }
        }
        
        return counter;
    }

  • fencullen
     + 0 comments

    C# O(n)

    public static int hackerlandRadioTransmitters(List<int> houses, int range)
{
    houses.Sort();
    
    int transmittersCount = 0;
    int i = 0;
    
    while (i < houses.Count)
    {
        transmittersCount++;
        
        // Take the first house. 
        int left = houses[i];
        int mid = left + range;
        
        // Find the first house out of range, put a transmitter 1 house before there.
        while (i < houses.Count && houses[i] <= mid)
        {
            i++;
        }
        
        mid = houses[i-1];
        int right = mid + range;
        
        // Find the first house out of range. Repeat.
        while (i < houses.Count && houses[i] <= right)
        {
            i++;
        }
    }
    
    return transmittersCount;
}

  • vivekkrg
     + 0 comments

    Here is the approch for O(n) time complexity and O(n) space complexity.

    public static int hackerlandRadioTransmitters(List<Integer> x, int k) {
    // Write your code here
        if(x.size() < 1)
            return 0;
            
        int maxInd = x.stream().max(Comparator.comparingInt(Integer::intValue)).get();
        int minInd = x.stream().min(Comparator.comparingInt(Integer::intValue)).get();
        
        Set<Integer> houseIndex = new HashSet<>(x);
        int count = 0;
        int currentInd = minInd;
        while(currentInd <= maxInd) {
            if(houseIndex.contains(currentInd)) {
                count++;
                for(int i = k; i >= 0; i--) { // look for farthest house in range for radio installation 
                    if(houseIndex.contains(currentInd + i)) {
                        currentInd += i; //here radio installed
                        break;
                    }
                }
                currentInd += k;// till this range coverage is available
            }
            currentInd++; // move to find next house for coverage
        }
        return count;
    }