Flatland Space Stations HackerRank Solution in C, C++, Java, Python

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 1 km 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 it’s nearest space station.

For example, there are n=3 cities and m=1 of them has a space station, city 1. They occur consecutively along a route. City 2 is 2-1=1 unit away and city 3 is 3-1=2 units away. City 1 is 0 units from its nearest space station as one is located there. The maximum distance is 2.

Function Description

Complete the flatlandSpaceStations function in the editor below. It should return an integer that represents the maximum distance any city is from a space station.

flatlandSpaceStations has the following parameter(s):

n: the number of cities
c: an integer array that contains the indices of cities with a space station, 1-based indexing

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 having a space-station. These values are unordered and unique.

Output Format

Print an integer denoting the maximum distance that an astronaut in a Flatland city would need to travel to reach the nearest space station.

Sample Input 0

5 2
0 4

Sample Output 0

2

Flatland Space Stations HackerRank Solution in C

#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 min[n];
    int i,j;
    int *c = malloc(sizeof(int) * m);
    for(int c_i = 0; c_i < m; c_i++){
       scanf("%d",&c[c_i]);
    }
    for(int i=0;i<n;i++) {
        min[i]=INT_MAX;
        for(j=0;j<m;j++) {
            if(abs(i-c[j]) < min[i])
                min[i]=abs(i-c[j]);
        }
       // printf("%d\n", min[i]);
    }
    int max = INT_MIN;
    for(i=0; i<n; i++) {
        if(min[i] > max)
            max = min[i];
    }
    printf("%d", max);
    return 0;
}

 

Flatland Space Stations HackerRank Solution in C++

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>

using namespace std;


int main(){
    int n;
    int m;
    cin >> n >> m;
    vector<int> c(m);
    for(int c_i = 0;c_i < m;c_i++){
       cin >> c[c_i];
    }
    sort(c.begin(), c.end());
    vector<int> dist(n);
    int last = -1000000;
    int cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur < m && c[cur] == i) {
            cur++;
            last = i;
        }
        dist[i] = i - last;
    }
    cur = m-1;
    last = 1000000;
    for (int i = n-1; i >= 0; i--) {
        if (cur >= 0 && c[cur] == i) {
            cur--;
            last = i;
        }
        dist[i] = min(dist[i], last - i);
    }
    printf("%d\n", *max_element(dist.begin(), dist.end()));
    return 0;
}

 

Flatland Space Stations HackerRank Solution in Java

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int c[] = new int[m];
        for(int c_i=0; c_i < m; c_i++){
            c[c_i] = in.nextInt();
        }
        Arrays.sort(c);
        int max = c[0];
        for (int i = 1; i < c.length; ++i) {
            int diff = c[i] - c[i - 1];
            int length = diff / 2;
            max = Math.max(max, length);
        }
        max = Math.max(max, n - c[c.length - 1] - 1);
        System.out.println(max);
    }
}

 

Flatland Space Stations HackerRank Solution in Python

#!/bin/python

import sys

n,m = raw_input().strip().split(' ')
n,m = [int(n),int(m)]
c = sorted(map(int,raw_input().strip().split(' ')))

last = 0
res = c[0]
for x in c:
    res = max(res, (x-last)/2)
    last = x
res = max(res, (n-1-last))
print res

 

Flatland Space Stations HackerRank Solution in C#

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {

    static void Main(String[] args) {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int n = Convert.ToInt32(tokens_n[0]);
        int m = Convert.ToInt32(tokens_n[1]);
        string[] c_temp = Console.ReadLine().Split(' ');
        int[] c = Array.ConvertAll(c_temp,Int32.Parse);
        
        Array.Sort(c);
        
        int max_distance = 0;
           
        for(int i = 0; i < n; i++){
            int left_d = n-1;
            int right_d = n-1;
            if(i > 0){
                for(int j = 0; j < m; j++){
                    if(c[j] > i)
                        break;
                    left_d = i - c[j];
                }
            }
                
            if(i < n){
                for(int j = m-1; j >= 0; j--){
                    if(c[j] < i)
                        break;
                    right_d = c[j] - i;
                }
            }
            
            max_distance = Math.Max(max_distance, Math.Min(left_d,right_d));
        }
        
        Console.WriteLine(max_distance);
    }
}

 

Attempt Flatland Space Stations HackerRank Challenge

Link – https://www.hackerrank.com/challenges/flatland-space-stations/

Next HackerRank Challenge Solution 

Link – https://exploringbits.com/fair-rations-hackerrank-solution/