Table of Contents
Minimum MST Graph – 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++ Minimum MST Graph HackerRank Solution
#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
void run()
{
ll N, M, S;
cin >> N >> M >> S;
ll blen = S - (N - 2);
ll nedge = ((N - 1) * (N - 2)) / 2;
ll ans;
if (M > nedge)
{
ll bremain = M - nedge;
if ((N - 1) * bremain < M)
{
ans = nedge + (M - nedge) * blen;
}
else
{
ll cval = S - (N - 1);
ans = M + (M * (cval / (N - 1)));
cval %= N - 1;
ll lval = cval * bremain;
ll rval = 1e18;
if (cval)
{
rval = bremain + (cval - 1) * (N - 2) - (cval - 1) * (cval - 2) / 2;
}
ans += min (lval, rval);
}
}
else
{
ans = (M - 1) + blen;
}
cout << ans << "\n";
}
int main()
{
int ntest; cin >> ntest;
for (int test = 0; test < ntest; test++)
run();
}
Java Minimum MST Graph HackerRank Solution
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.io.BufferedReader;
import java.io.InputStream;
/**
* Built using CHelper plug-in
* Actual solution is at the top
*/
public class Solution {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
OutputWriter out = new OutputWriter(outputStream);
MinimumMSTGraph solver = new MinimumMSTGraph();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}
static class MinimumMSTGraph {
public int MAGIC = 100;
public void solve(int testNumber, InputReader in, OutputWriter out) {
long n = in.nextLong();
long m = in.nextLong();
long s = in.nextLong();
m -= n - 1;
long add1 = (n - 1) * (n - 2) / 2 - (n - 2);
long take = Math.min(m, add1);
m -= take;
long light = 1;
long heavy = s - light * (n - 2);
BigInteger ans = new BigInteger(String.valueOf(s));
ans = ans.add(new BigInteger(String.valueOf(light)).multiply(new BigInteger(String.valueOf(take))));
ans = ans.add(new BigInteger(String.valueOf(heavy)).multiply(new BigInteger(String.valueOf(m))));
if (m == 0) {
out.println(ans);
return;
}
m += take + n - 1;
long lo = 1;
long hi = n - 1;
long iter = MAGIC;
while (hi >= lo && iter-- > 0) {
BigInteger w = getCost(hi, s, m, n);
if (w.compareTo(ans) < 0) ans = w;
hi--;
}
iter = MAGIC;
while (lo <= hi && iter-- > 0) {
BigInteger w = getCost(lo, s, m, n);
if (w.compareTo(ans) < 0) ans = w;
lo++;
}
out.println(ans);
}
public BigInteger getCost(long i, long s, long m, long n) {
long need = s - (n - 1);
BigInteger ccost = new BigInteger(String.valueOf(m));
long n1 = m - i * (i - 1) / 2;
long d1 = n - i;
ccost = ccost.add(new BigInteger(String.valueOf((need / d1))).multiply(new BigInteger(String.valueOf(n1))));
need %= d1;
if (need > 0) {
long ax = n - need;
BigInteger a1 = new BigInteger(String.valueOf(m - ax * (ax - 1) / 2));
BigInteger a2 = new BigInteger(String.valueOf(need)).multiply(new BigInteger(String.valueOf(m - (n - 1) * (n - 2) / 2)));
if (a1.compareTo(a2) < 0) ccost = ccost.add(a1);
else ccost = ccost.add(a2);
}
return ccost;
}
}
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public long nextLong() {
return Long.parseLong(next());
}
}
static class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
}
public void println(Object... objects) {
print(objects);
writer.println();
}
public void close() {
writer.close();
}
}
}
Python 3 Minimum MST Graph HackerRank Solution
#!/bin/python3
import sys
g = int(input().strip())
for a0 in range(g):
n,m,s = input().strip().split(' ')
n,m,s = [int(n),int(m),int(s)]
if m <= (n - 1) * (n - 2) // 2 + 1:
print(m + s - n + 1)
else:
s -= n - 1
e = m - (n - 1) * (n - 2) // 2
mnc = (s + n - 2) // (n - 1)
ans = 1e42
s -= mnc
for A in [0, s // (n - 2), s // (n - 2) - 1]:
for B in [0, n - 3, (s - A * (n - 2)) % (n - 2)]:
x = A * (n - 2) + B
if 0 <= x <= s:
ans = min(ans, (s - x + mnc) * e + (n - 1) * (n - 2) // 2 * A + B * (B - 1) // 2 + B * (n - B - 1))
print(ans + m)
Python 2 Minimum MST Graph HackerRank Solution
t = int(raw_input())
def calc1(n, m, s):
a = 1
b = s - (n - 2)
c1 = n - 2
c2 = 1
e = n - 1
cur = s
if c1 * (c1 - 1) / 2 + e >= m:
return cur + a * (m - e)
else:
e += c1 * (c1 - 1) / 2
cur += (c1 * (c1 - 1) / 2) * a
return cur + (m - e) * b
def calc2(n, m, s):
a = s / (n - 1)
b = a + 1
c1 = n - 1 - s % (n - 1)
e = n - 1
cur = s
if c1 * (c1 - 1) / 2 + e >= m:
return cur + a * (m - e)
else:
e += c1 * (c1 - 1) / 2
cur += (c1 * (c1 - 1) / 2) * a
return cur + (m - e) * b
def calc3(n, m, s):
a = s / (n - 1)
b = a + s % (n - 1)
c1 = n - 2
e = n - 1
cur = s
if c1 * (c1 - 1) / 2 + e >= m:
return cur + a * (m - e)
else:
e += c1 * (c1 - 1) / 2
cur += (c1 * (c1 - 1) / 2) * a
return cur + (m - e) * b
for test in xrange(t):
n, m, s = map(int, raw_input().split())
if n == 2:
print s
else:
print min(calc1(n, m, s), calc2(n, m, s), calc3(n, m, s))
C Minimum MST Graph HackerRank Solution
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
typedef long long ll;
ll min(ll l,ll m)
{
if(l>m)
return m;
else
return l;
}
void run()
{
ll N, M, S;
scanf("%lld%lld%lld",&N,&M,&S);
//cin >> N >> M >> S;
ll blen = S - (N - 2);
ll nedge = ((N - 1) * (N - 2)) / 2;
ll ans=0;
if (M > nedge)
{
ll bremain = M - nedge;
if ((N - 1) * bremain < M)
{
ans = nedge + (M - nedge) * blen;
}
else
{
ll cval = S - (N - 1);
ans = M + (M * (cval / (N - 1)));
cval %= N - 1;
ll lval = cval * bremain;
ll rval = INT_MAX;
if (cval)
{
rval = bremain + (cval - 1) * (N - 2) - (cval - 1) * (cval - 2) / 2;
}
ans += min (lval, rval);
}
}
else
{
ans = (M - 1) + blen;
}
printf("%lld\n",ans);
// cout << ans << "\n";
}
int main()
{
int ntest,test;
scanf("%d",&ntest);
// cin >> ntest;
for (test = 0; test < ntest; test++)
run();
}
Leave a comment below
