HackerRank Flatland Space Stations Solution

In this post, we will solve HackerRank Flatland Space Stations Problem Solution.

Flatland is a country with a number of cities, some of which have space stations. Cities are numbered consecutively and each has a road of 1km length connecting it to the next city. It is not a circular route, so the first city doesn’t connect with the last city. Determine the maximum distance from any city to its nearest space station.
Example
n = 3
c = [1]
There are n = 3 cities and city 1 has a space station. They occur consecutively along a route. City 0 is 1-0 = 1 unit away and city 2 is 2-1 = 1 units away. City 1 is 0 units from its nearest space station as one is located there. The maximum distance is 1.

Function Description

Complete the flatlandSpaceStations function in the editor below.

flatlandSpaceStations has the following parameter(s):

int n: the number of cities
int c[m]: the indices of cities with a space station

Returns
– int: the maximum distance any city is from a space station

Input Format
The first line consists of two space-separated integers, n and m.
The second line contains m space-separated integers, the indices of each city that has a
space-station. These values are unordered and distinct.

Output Format

Sample Input 0

STDIN   Function
-----   --------
5 2     n = 5, c[] size m = 2
0 4     c = [0, 4]

Sample Output 0

The distance to the nearest space station for each city is listed below:

c[0] has distance 0 km, as it contains a space station.
c[1] has distance 1 km to the space station in c[0].
c[2] has distance 2 km to the space stations in c[0] and c[4].
c[3] has distance 1 km to the space station in c[4].
c[4] has distance 0 km, as it contains a space station.
We then take max(0, 1, 2, 1, 0) = 2.

Sample Input 1

6 6
0 1 2 4 3 5

Sample Output 1

Explanation 1

In this sample, n = m so every city has space station and we print 0 as our answer.

Table of Contents

Flatland Space Stations C Solution

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

int main(){
    int n; 
    int m; 
    scanf("%d %d",&n,&m);
    int *c = malloc(sizeof(int) * (m));
    for(int c_i = 0; c_i < m; c_i++){
       scanf("%d",&c[c_i]);
    }
    
    qsort(c, m, sizeof(int), cmpfunc);
    
    int max = 0;
    int i, isStart = 0, isEnd = 0;
    
    for(i = 1; i < (m); i++){
        if(c[i] - c[i-1] > max)
            max = c[i] - c[i-1];
        if(!isEnd)
            isEnd = (c[i] == n-1);
        if(!isStart)
            isStart = (c[i] == 0);
    }
    max /= 2;
    if(!isStart && (c[0]-0 > max)){
        max = c[0];
    }
    if(!isEnd && ((n-1 - c[m-1]) > max)){
        max = n-1 - c[m-1];
    }
    
    printf("%d\n", max);

    
    return 0;
}

Flatland Space Stations C++ Solution

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

template <class T>
T input(std::istream& input = std::cin) {
  T value;
  input >> value;
  return value;
}

template <typename T>
constexpr T ceil_div(T x, T y) {
  return x / y + (x % y == 0 ? 0 : 1);
}

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);
  const auto num_cities = input<size_t>();
  const auto num_stations = input<size_t>();

  vector<size_t> stations(num_stations);
  for (auto& elem : stations) {
    cin >> elem;
  }
  sort(begin(stations), end(stations));

  size_t max_dist = max(stations.front(), (num_cities - 1) - stations.back());
  for (size_t i = 0; i + 1 < stations.size(); ++i) {
    const auto region_size = stations[i + 1] - (stations[i] + 1);
    max_dist = max(max_dist, ceil_div<size_t>(region_size, 2));
  }

  cout << max_dist << '\n';
}

Flatland Space Stations C Sharp Solution

using System;
class Solution {

    static void Main(String[] args) {
        string[] tokens_01 = Console.ReadLine().Split(' ');
        string[] tokens_02 = Console.ReadLine().Split(' ');
        int   nn = Convert.ToInt32(tokens_01[0]);
        int[] cc = Array.ConvertAll(tokens_02, Int32.Parse);

        Array.Sort(cc);
        int max = 0;
        for (int kk = 0; kk < nn; kk++) {
            int zz = Array.BinarySearch(cc, kk);
            int n1 = 0;
            if (zz < 0) {
                zz = ~zz;
                if (zz == 0) {
                    n1 = Math.Abs(kk - cc[0]);
                } else if ( zz == cc.Length ) {
                    n1 = Math.Abs(kk - cc[cc.Length - 1]);
                } else {
                    n1 = Math.Min( Math.Abs(kk - cc[zz - 1] ) , Math.Abs(kk - cc[zz]) );
                }
            }
            max = Math.Max(max, n1);
        }
        System.Console.WriteLine(max);
    }
}

Flatland Space Stations Java Solution

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.stream.IntStream;

public class SpaceStations {

    static int flatlandSpaceStations(int n, int[] c) {
        List<Integer> closests = new ArrayList<>();
        int min = n;
        for(int i=0;i<n;i++){
            min = n;
            for(int j=0;j<c.length;j++){
                min = Math.min(min,Math.abs(i-c[j]));
            }
            closests.add(min);
        }
        
        var max = closests.stream().max(Integer::compare);
        if(max.isPresent()){
            return max.get();
        }else{
            return 0;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int l = sc.nextInt();
        int[] arr = new int[l];
        for(int i=0;i<l;i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(flatlandSpaceStations(n, arr));
    }    
}

Flatland Space Stations JavaScript Solution

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Solution {

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        String[] enAndKay = bufferedReader.readLine().split(" ");
        int n = Integer.parseInt(enAndKay[0]);
        int k = Integer.parseInt(enAndKay[1]);

        String[] statsString = bufferedReader.readLine().split(" ");
        int[] stations = new int[k];
        for (int i = 0; i < stations.length; i++) {
            stations[i] = Integer.parseInt(statsString[i]);
        }

        Arrays.sort(stations);

        int result = 0;
        result = Math.max(result, stations[0]);
        result = Math.max(result, n - 1 - stations[stations.length - 1]);
        for (int i = 1; i < stations.length; i++) {
            result = Math.max(result, (stations[i] - stations[i - 1]) / 2);
        }
        System.out.println("" + result);
    }
}

Flatland Space Stations Python Solution

#!/bin/python3

import sys


n,m = input().strip().split(' ')
n,m = [int(n),int(m)]
c = [int(c_temp) for c_temp in input().strip().split(' ')]
c = sorted(c)
maxs = c[0]
for i in range(1,len(c)):
    x = (c[i] - c[i-1])>>1
    if maxs < x:
        maxs = x
if n - c[len(c)-1] - 1 > maxs:
    maxs = n - c[len(c)-1] - 1
print(maxs)