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. Prepare
  2. Algorithms
  3. Search
  4. Hackerland Radio Transmitters
  5. Discussions

Hackerland Radio Transmitters

  • nctam1807
     + 0 comments

    Kotlin solution. I find the max value (the farthest position of the house) of the x array first. Then I use that value to minimize the memory usage of the array created for counting sorting the x array. The result array from the counting sort will be used to determine the minimum number of transmitter needed.

    fun hackerlandRadioTransmitters(x: Array<Int>, k: Int): Int {
    var max = 0
    for (pos in x) {
        max = Math.max(max, pos)
    }
    
    val positions = Array<Boolean>(max+1){false}
    x.forEach { pos->
        positions[pos] = true
    }
    
    var count = 0
    var i = 1
    while (i < positions.size) {
        if (!positions[i]) {
            i++
        } else {
            var center = i+k
            while (center >= i) {
                if (center < positions.size && positions[center]) {
                    count++
                    i=center+k+1
                } else {
                    center--
                }
            }
        }
    }
    
    return count
}