In this HackerRank Flatland Space Stations problem 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.

HackerRank Flatland Space Stations problem solution


Problem solution in Python programming.

#!/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.sort()
maxgap = max(a-b for a, b in zip(c[1:], c)) if len(c) > 1 else 0
ans = max(maxgap//2, c[0], n-1-c[-1])
print(ans)


Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int M = in.nextInt();
        int[] list = new int[M];
        for(int i = 0; i < M; i++) {
            list[i] = in.nextInt();
        }
        Arrays.sort(list);
        
        int first = Math.abs(0 - list[0]);
        int last = Math.abs((N - 1) - list[M-1]);
        int max = Math.max(first, last);
        int maxSpace = 0;
        for(int i = 0; i < M - 1; i++) {
            maxSpace = Math.max(Math.abs(list[i] - list[i+1]), maxSpace);
        }
        max = Math.max(max, maxSpace / 2);
        System.out.println(max);
    }
}


Problem solution in C++ programming.

#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

int main() {
    int n; int m;
    while(~scanf("%d%d", &n, &m)) {
        vector<bool> ok(n);
        for(int i = 0; i < m; ++ i) {
            int c;
            scanf("%d", &c);
            ok[c] = true;
        }
        vi dist(n, INF);
        int p = -INF;
        rep(i, n) {
            if(ok[i]) p = i;
            amin(dist[i], i - p);
        }
        p = INF;
        for(int i = n - 1; i >= 0; -- i) {
            if(ok[i]) p = i;
            amin(dist[i], p - i);
        }
        int ans = *max_element(all(dist));
        printf("%d\n", ans);
    }
    return 0;
}


Problem solution in C programming.

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

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]);
    }
    
    int min;
    int max = 0;
    for (int i = 0; i < n; i++) {
        min = n;
        for (int c_i = 0; c_i < m; c_i++) {
            if (abs(c[c_i] - i) < min) {
                min = abs(c[c_i]-i);
            }
        }
        if (min > max) {
            max = min;
        }
    }
    printf("%d\n", max);
    return 0;
}


Problem solution in JavaScript programming.

process.stdin.resume();
process.stdin.setEncoding('ascii');

var input_stdin = "";
var input_stdin_array = "";
var input_currentline = 0;

process.stdin.on('data', function (data) {
    input_stdin += data;
});

process.stdin.on('end', function () {
    input_stdin_array = input_stdin.split("\n");
    main();    
});

function readLine() {
    return input_stdin_array[input_currentline++];
}

/////////////// ignore above this line ////////////////////

function main() {
    var n_temp = readLine().split(' ');
    var n = parseInt(n_temp[0]);
    var m = parseInt(n_temp[1]);
    c = readLine().split(' ');
    c = c.map(Number);
	var longestSpan=0;
	c.sort( (a,b) => a-b );
	for( var ii = 0; ii < m-1; ii++) longestSpan = Math.max(longestSpan, c[ii+1]-c[ii]);
	var longestHike = Math.floor(longestSpan / 2);
	var left  = c[0]   === 0 ? 0 : c[0];
	var right = c[m-1] === n-1 ? 0 : n-1 - c[m-1];
	longestHike = Math.max(longestHike, left, right );  // edge cases
	process.stdout.write(longestHike.toString()); 
}