HackerRank Flatland Space Stations problem solution

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.

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()); 
}