Skip to content
Programming101
Programming101

Learn everything about programming

  • Home
  • CS Subjects
    • IoT – Internet of Things
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programming101
Programming101

Learn everything about programming

HackerRank Diameter Minimization problem solution

YASH PAL, 31 July 2024

In this HackerRank Diameter Minimization problem solution we have given two integers, n, and m, to build a strongly connected oriented graph with n vertices where each vertex has outdegree m and the graph’s diameter is as small as possible (see the Scoring section below for more detail). Then print the graph according to the Output Format specified.

HackerRank Diameter Minimization problem solution

Problem solution in Python.

#!/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)

{“mode”:”full”,”isActive”:false}

Problem solution in Java.

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

public class Solution {

  static Deque<Integer> q = new LinkedList<>();

  static int[] dis = new int[1001];

  static int bfs(int n, int m, int x) {
    Arrays.fill(dis, 1_000_000_000);
    dis[x] = 0;
    q.add(x);
    int mmh = 0;
    while (!q.isEmpty()) {
      int k = q.removeFirst();
      mmh = dis[k];
      for (int i = 0; i < m; i++) {
        int j = (k * m + i) % n;
        if (dis[j] > mmh + 1) {
          dis[j] = mmh + 1;
          q.add(j);
        }
      }
    }
    return mmh;
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int m = Integer.parseInt(st.nextToken());

    dis = new int[n];
    
    int mmh = 0;
    for (int i = 0; i < n; i++) {
      mmh = Math.max(mmh, bfs(n, m, i));
    }
    bw.write(mmh + "n");
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
        bw.write((i * m + j) % n + " ");
      }
      bw.write("n");
    }

    bw.newLine();

    bw.close();
    br.close();
  }
}

{“mode”:”full”,”isActive”:false}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;
#define sz(x) ((int) (x).size())
#define forn(i,n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef long long i64;
typedef long double ld;
const int inf = int(1e9) + int(1e5);
const ll infl = ll(2e18) + ll(1e10);

int calcBest(int n, int m) {
    int d = 0;
    int onD = 1;
    int cn = 1;
    while (cn < n) {
        onD *= m;
        ++d;
        cn += onD;
    }
    return d;
}

const int maxn = 1005;
int g[maxn][maxn];
int n, m;

int dist[maxn];
int calcDiam(int s) {
    fill(dist, dist + n, inf);

    vector<int> q;
    dist[s] = 0;
    q.push_back(s);
    forn (ii, sz(q)) {
        int u = q[ii];
        forn (i, m) {
            int v = g[u][i];
            if (dist[v] < inf)
                continue;
            dist[v] = dist[u] + 1;
            q.push_back(v);
        }
    }

    if (sz(q) < n)
        return inf;
    return dist[q.back()];
}

int main() {
    #ifdef LOCAL
    assert(freopen("test.in", "r", stdin));
    #endif
    cin >> n >> m;
    forn (i, n) {
        forn (j, m)
            g[i][j] = (i * m + j) % n;
    }
    int diam = 0;
    forn (i, n)
        diam = max(diam, calcDiam(i));
    int best = calcBest(n, m);
    //cerr << "best " << best << 'n';
    assert(diam <= best + 1);
    assert(diam >= best);

    cout << diam << 'n';
    forn (i, n) {
        forn (j, m)
            cout << g[i][j] << ' ';
        cout << 'n';
    }
}

{“mode”:”full”,”isActive”:false}

Algorithms coding problems solutions

Post navigation

Previous post
Next post
  • HackerRank Separate the Numbers solution
  • How AI Is Revolutionizing Personalized Learning in Schools
  • GTA 5 is the Game of the Year for 2024 and 2025
  • Hackerrank Day 5 loops 30 days of code solution
  • Hackerrank Day 6 Lets Review 30 days of code solution
How to download udemy paid courses for free

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
©2025 Programming101 | WordPress Theme by SuperbThemes