Hello Programmers, In this post, you will know how to solve the HackerRank Flatland Space Stations Solution. This problem is a part of the HackerRank Algorithms Series.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Hackerrank by yourself. If you find any difficulty after trying several times, then you can look for solutions.
HackerRank Flatland Space Stations Solution
Task
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.
Constraints
- 1 <= n <= 105
- 1 <= m <= n
- There will be at least 1 city with a space station.
- No city has more than one space station.
Output Format
Sample Input 0
STDIN Function ----- -------- 5 2 n = 5, c[] size m = 2 0 4 c = [0, 4]
Sample Output 0
2
Explanation 0
This sample corresponds to following graphic:
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
0
Explanation 1
In this sample, n = m so every city has space station and we print 0 as our answer.
HackerRank Flatland Space Stations Solution
Flatland Space Stations 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 Solution in Cpp
#include <bits/stdc++.h>
using namespace std;
namespace stuff {
typedef long long ll;
const int INF = int(1e9);
void solve(int test_num) {
int N, M;
cin >> N >> M;
vector<bool> space(N, false);
for (int i = 0, city; i < M; ++i) {
cin >> city;
space[city] = true;
}
vector<int> dist(N);
for (int i = 0, pred = -INF; i < N; ++i) {
if (space[i]) {
pred = i;
}
dist[i] = i - pred;
}
for (int i = N - 1, pred = INF; i >= 0; --i) {
if (space[i]) {
pred = i;
}
dist[i] = min(dist[i], pred - i);
}
const int res = *max_element(dist.begin(), dist.end());
cout << res << endl;
}
void solve() {
#ifdef AZN
//make_case();
double start_t = clock();
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
//freopen("azn.txt", "w", stderr);
#endif
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
// scanf("%d", &T);
// cin >> T;
for (int t = 1; t <= T; t++)
solve(t);
#ifdef AZN
cerr << fixed << setprecision(3) << "Took: " << ((clock() - start_t) / CLOCKS_PER_SEC) << endl;
#endif
}
}
int main() {
stuff::solve();
return 0;
}Flatland Space Stations Solution in Java
import java.io.*;
import java.util.*;
public class Solution {
private BufferedReader in;
private StringTokenizer line;
private PrintWriter out;
public void solve() throws IOException {
int n = nextInt();
int m = nextInt();
int[] a = nextIntArray(m);
Arrays.sort(a);
int res = Math.max(a[0], n - 1 - a[m - 1]);
for (int i = 1; i < m; i++) {
res = Math.max(res, (a[i] - a[i - 1]) / 2);
}
out.println(res);
}
public static void main(String[] args) throws IOException {
new Solution().run(args);
}
public void run(String[] args) throws IOException {
if (args.length > 0 && "DEBUG_MODE".equals(args[0])) {
in = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
} else {
in = new BufferedReader(new InputStreamReader(System.in));
}
out = new PrintWriter(System.out);
// out = new PrintWriter("output.txt");
// int t = nextInt();
int t = 1;
for (int i = 0; i < t; i++) {
// out.print("Case #" + (i + 1) + ": ");
solve();
}
in.close();
out.flush();
out.close();
}
private int[] nextIntArray(int n) throws IOException {
int[] res = new int[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
private long[] nextLongArray(int n) throws IOException {
long[] res = new long[n];
for (int i = 0; i < n; i++) {
res[i] = nextInt();
}
return res;
}
private int nextInt() throws IOException {
return Integer.parseInt(nextToken());
}
private long nextLong() throws IOException {
return Long.parseLong(nextToken());
}
private double nextDouble() throws IOException {
return Double.parseDouble(nextToken());
}
private String nextToken() throws IOException {
while (line == null || !line.hasMoreTokens()) {
line = new StringTokenizer(in.readLine());
}
return line.nextToken();
}
private static class Pii {
private int key;
private int value;
public Pii(int key, int value) {
this.key = key;
this.value = value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Pii pii = (Pii) o;
if (key != pii.key) return false;
return value == pii.value;
}
@Override
public int hashCode() {
int result = key;
result = 31 * result + value;
return result;
}
}
private static class Pair<K, V> {
private K key;
private V value;
public Pair(K key, V value) {
this.key = key;
this.value = value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Pair<?, ?> pair = (Pair<?, ?>) o;
if (key != null ? !key.equals(pair.key) : pair.key != null) return false;
return !(value != null ? !value.equals(pair.value) : pair.value != null);
}
@Override
public int hashCode() {
int result = key != null ? key.hashCode() : 0;
result = 31 * result + (value != null ? value.hashCode() : 0);
return result;
}
}
}
Flatland Space Stations 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 resFlatland Space Stations Solution using JavaScript
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");
var result = main();
process.stdout.write(result);
});
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);
c.sort(function(left, right) {
return left - right;
});
if (n == m) {
return 0;
}
var max = Math.max(c[0], n - c[m - 1] - 1);
if (m == 1) {
return max;
}
for (var i = 0; i < m - 1; i++) {
max = Math.max(max, Math.floor((c[i + 1] - c[i]) / 2));
}
return max;
}Flatland Space Stations Solution in Scala
import math.{abs, min}
object Solution {
def main(args: Array[String]) {
val sc = new java.util.Scanner (System.in);
var n = sc.nextInt();
var m = sc.nextInt();
var c = new Array[Int](m);
for(c_i <- 0 to m-1) {
c(c_i) = sc.nextInt();
}
val cs = c.sorted
var j = 0
val mins = for(i <- 0 until n) yield {
if (j < cs.length - 1 && i > cs(j+1)) j += 1
if (j == cs.length - 1) abs(cs(j) - i)
else min(abs(cs(j) - i), abs(cs(j+1) - i))
}
println(mins.max)
}
}Flatland Space Stations Solution in Pascal
uses math; var n,m,res:longint; a,f:array[0..100009] of longint; Procedure ReadF; var i,x:longint; begin readln(n,m); for i:=1 to m do begin read(x); a[x+1]:=1; end; end; Procedure Process; var i,pre:longint; begin pre:=-1; for i:=1 to n do if a[i]=1 then begin f[i]:=0; pre:=i; end else if pre<>-1 then f[i]:=i-pre else f[i]:=maxlongint; pre:=-1; for i:=n downto 1 do if a[i]=1 then begin f[i]:=0; pre:=i; end else if pre<>-1 then f[i]:=min(f[i],pre-i); for i:=1 to n do res:=max(res,f[i]); write(res); end; begin ReadF; Process; end.
Disclaimer: This problem (Flatland Space Stations) is generated by HackerRank but the Solution is Provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.