Hackerland Radio Transmitters

Sort by

recency

|

39 Discussions

|

  • + 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;
        }
    
  • + 0 comments

    Here is HackerRland Radio transmitter problem solution in Python Java, c++ c and javascript

  • + 0 comments
    def hackerlandRadioTransmitters(x, k):
        size = len(x)
        if size == 1:
            return 1
            
        x.sort()
        num = 0
        i = 0
        while i < size:
            # mark the furthest location within the coverage at current i
            loc = x[i] + k
       
            # move to the furthest house within the range and set transmitter
            while i < size and x[i] <= loc:
                i += 1
            i -= 1
            num += 1
            
            # make the furthest location within the coverage at current i
            loc = x[i] + k
            
            # move to the first house outside the coverage
            while i < size and x[i] <= loc:
                i += 1
            
        return num
    
  • + 0 comments

    C++20

    int hackerlandRadioTransmitters(vector<int> x, int k) {
        sort(x.begin(), x.end());
        int n_radios = 0;
        int N = x.size();
        int house = 0;
        int i = 0;
        while(i < N){
            house = x[i];  // radio installed here
            while(i < N && x[i] <= house + k){
                i ++;
            }
            n_radios ++;
            house = x[i-1];  // radio installed here
            while(i < N && x[i] <= house + k){
                i ++;
            }
        }
        return n_radios;
    
  • + 0 comments
    Single Pass One Line 
    
    def hackerlandRadioTransmitters(x: Array[Int], k: Int): Int = 
        x.foldLeft((-1,-1,-1)) {
          case ((-1,-1,-1),_) => 
            x.sortInPlace
            (1,x(0),x(0)+k)
          case ((i,l,r),house) if house - k <= l => 
              (i,l,house+k)           
          case ((i,l,r),house) if house > r => 
              (i+1,house,house+k)
          case acc => acc._1
          }._1