Diameter Minimization – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Diameter Minimization HackerRank Solution
#include <iostream>
#include <cmath>
#include <queue>
#include <vector>
using namespace std;
class Graph {
private:
int size;
int* vertices;
vector<int>* adj_list;
public:
Graph(int n) {
size = n;
vertices = new int[n];
adj_list = new vector<int>[n];
}
void add_edge(int u, int v) {
adj_list[u].push_back(v);
}
void print_adj_list() {
for(int u = 0; u < size; u++) {
for(int v : adj_list[u]) {
cout << v << " ";
}
cout << endl;
}
}
int max_of_min_distances_from_start(int start) {
// Initialize distances
vector<int> distances(size);
for(int i = 0; i < size; i++) {
distances[i] = -1;
}
// Initialize queue for BFS
queue<int> v_queue;
v_queue.push(start);
distances[start] = 0;
// Start Breadth First Search
while(!v_queue.empty()) {
int current_v = v_queue.front();
v_queue.pop();
for(int i = 0; i < adj_list[current_v].size(); i++) {
if(distances[adj_list[current_v][i]] == -1) {
distances[adj_list[current_v][i]] = distances[current_v] + 1;
v_queue.push(adj_list[current_v][i]);
}
}
}
// Find max distance (if the graph is not strongly connected the solution is wrong)
int max_d = 0;
for(int i = 0; i < size; i++) {
if(distances[i] > max_d)
max_d = distances[i];
}
return max_d;
}
};
int main() {
int n, m;
cin >> n >> m;
Graph graph(n);
// Modular heap
int add = 0;
for(int i = 0; i < n; i++) {
for(int j = 1; j <= m; j++) {
int child = (m * i + j + add) % n;
if(child == i) {
child = (child + 1) % n;
add++;
}
graph.add_edge(i, child);
}
}
// Find diameter
int diam = -1, max_from_start;
for(int start = 0; start < n; start++) {
max_from_start = graph.max_of_min_distances_from_start(start);
if(max_from_start > diam)
diam = max_from_start;
}
// Print solution
cout << diam << endl;
graph.print_adj_list();
return 0;
}
Java Diameter Minimization HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
static int[] stack = new int[1100];
static int[] visited = new int[1100];
static int diameter(int[][] g, int b) {
for (int i = 0; i < g.length; i++) {
visited[i] = -1;
}
stack[0] = b;
visited[b] = 0;
int d = 0;
int c = 0;
int v = 1;
while(c < v) {
int p = stack[c];
for (int i = 0; i < g[p].length; i++) {
int q = g[p][i];
if(visited[q] < 0) {
visited[q] = visited[p] + 1;
stack[v] = q;
v++;
if(visited[q] > d) {
d = visited[q];
}
}
}
c++;
}
if(v < g.length) throw new RuntimeException("Visited " + v + " out of " + g.length);
return d;
}
static int diameter(int[][] g) {
int d = 0;
for (int i = 0; i < g.length; i++) {
int di = diameter(g, i);
if(di > d) d = di;
}
return d;
}
static int[][] generateGraph(int n, int m) {
int[] b = getK(n, m);
int n1 = n / m;
if(n < 10) n1 = n; else {
n1 = b[1];
if(seed.nextDouble() < 0.5 && n1 * m < n) n1 = n1 * m;
}
int[][] g = new int[n][m];
int l = 1;
for (int p = 0; p < n; p++) {
int s = 0;
for (int i = 0; i < m; i++) {
if(l < n) {
g[p][i] = l;
l++;
} else {
g[p][i] = s;
if(s > 0) g[p][i] = seed.nextInt(n1);
if(s + 1 < n) s++;
}
}
}
return g;
}
static int[] getK(int n, int m) {
int leaves = n - (n + m - 1) / m;
if(m > 1 && n > 10){
return new int[]{1, (n - leaves) };
}
int[] ps = new int[11];
ps[0] = 1;
int s = 1;
int l = 1;
int b = 0;
int e = 0;
while(true) {
ps[l] = ps[l-1] * m;
if(ps[l] * ps[l] < leaves * (m - 1)) {
b = s;
e = b + ps[l];
}
s += ps[l];
if(s >= n) {
ps[l] = ps[l] - s + n;
break;
} else {
l++;
}
}
return new int[]{b, e};
}
static int[][] generateGraph1(int n, int m, int h) {
if(h > n / 2) h = n / 2;
int[] b = getK(n, m);
int[][] g = new int[n][m];
int l = 1;
int q = b[0];
for (int p = 0; p < n; p++) {
int s = 0;
for (int i = 0; i < m; i++) {
if(l < n) {
g[p][i] = l;
l++;
} else {
g[p][i] = s;
if(s > 0 || p % h != 0) {
g[p][i] = q;
q++;
if(q == b[1]) q = b[0];
} else {
if(s + 1 < n) s++;
}
}
}
}
return g;
}
static void print(int[][] g, int n, int m) {
int d = diameter(g);
System.out.println(d);
for (int p = 0; p < n; p++) {
for (int i = 0; i < m; i++) {
if(i > 0) System.out.print(" ");
System.out.print(g[p][i]);
}
System.out.println("");
}
}
static Random seed = new Random();
static void run() {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
long t = System.currentTimeMillis();
int[][] g = generateGraph(n, m);
int d = diameter(g);
for (int h = 1; h < n / 3 && h < 30; h++) {
try {
int[][] gi = generateGraph1(n, m, h);
int di = diameter(gi);
if(di < d) {
g = gi;
d = di;
}
long dt = System.currentTimeMillis() - t;
if(dt > 700) break;
} catch (Exception e) {
break;
}
}
for (int i = 0; i < 5000; i++) {
int[][] gi = generateGraph(n, m);
int di = diameter(gi);
if(di < d) {
g = gi;
d = di;
}
long dt = System.currentTimeMillis() - t;
if(dt > 1000) break;
}
print(g, n, m);
}
public static void main(String[] args) {
run();
}
}
Python 3 Diameter Minimization HackerRank Solution
import sys, time, random
from time import time
from collections import *
from decimal import *
from math import *
from bisect import *
#from deque import *
def eprint(*args, **kwargs):
print(*args, file=sys.stderr, **kwargs)
t0 = time()
#N, D = 787, 3
N, D=[int(i) for i in input().strip().split(' ')]
RN=range(N)
RD=range(D)
MINDIAM=1
NN=D
while NN < N: NN *=D; MINDIAM+=1
eprint("MINDIAM=",MINDIAM)
out=[[] for n in RN]
def diam(n0):
dis=[9999]*N
q = deque()
for o in out[n0]:
dis[o]=1
q.append(o)
while len(q):
n = q.popleft()
dd=dis[n]+1
for o in out[n]:
if dis[o] <= dd: continue
dis[o]=dd
q.append(o)
r=max(dis)
#eprint("dis[%d]=" % n0, dis)
#eprint("diam[%d]="%n0,r, " mind=",md)
return r
def diamall():
lo=N
hi=0
for n in RN:
d=diam(n)
lo=min(lo, d)
hi=max(hi, d)
eprint("DIAMALL:",lo,hi)
return hi
o=1
for n in RN:
for d in RD:
out[n].append(o)
o+=1
if o==N: o=0
ans=diamall()
eprint("t=", time()-t0)
print(ans)
for n in RN:
print(*out[n])
#if n>10: eprint("BREAK"); break
Python 2 Diameter Minimization HackerRank Solution
#!/bin/python3
import sys
import math
def opt_diameter(n, m):
count = 1
depth = 0
while count < n:
depth += 1
count = m ** depth
return depth
def diameter(n, m):
count = 1
depth = 0
while count < n:
depth += 1
count += m ** depth
left_over = m ** depth - (count - n)
limit = m ** (depth - 1)
discount = 1
if left_over > limit:
discount = 0
return max(depth, 2 * depth - discount)
def solve(in_file, out_file):
n, m = (int(raw) for raw in in_file.readline().strip().split(' '))
out_file.write("{}\n".format(opt_diameter(n, m)))
count = 0
for _ in range(n):
ret = []
for _ in range(m):
val = count % n
count += 1
ret.append(str(val))
out_file.write("{}\n".format(" ".join(ret)))
if __name__ == '__main__':
from_file = False
if from_file:
path = 'Data\\'
name = 'mega_prime'
file_input = open(path + name + '.in', 'r')
file_output = open(path + name + '.out','w')
solve(file_input, file_output)
file_input.close()
file_output.close()
else:
solve(sys.stdin, sys.stdout)
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
