Table of Contents
Problem solving – 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++ Problem solving HackerRank Solution
#include <iostream>
#include <cstring>
#include <cmath>
#include <vector>
using namespace std;
int N,K;
int v[310],match[310],inv[310];
vector<int> adj[310];
bool vis[310];
bool augment(int x)
{
if(vis[x])return false;
vis[x] = true;
for(int i = 0; i < adj[x].size(); i++)
{
if((inv[adj[x][i]] == -1 || augment(inv[adj[x][i]])))
{
match[x] = adj[x][i];
inv[adj[x][i]] = x;
return true;
}
}
return false;
}
int main()
{
int T;
cin >> T;
for(int t = 0; t < T; t++)
{
cin >> N >> K;
for(int i = 0; i < N; i++)
{
adj[i].clear();
cin >> v[i];
}
for(int i = 0; i < N; i++)
{
for(int j = i+1; j < N; j++)
{
if(abs(v[i]-v[j]) >= K)
{
adj[i].push_back(j);
}
}
}
memset(match,-1,sizeof(match));
memset(inv,-1,sizeof(inv));
int ans = 0;
for(int i = 0; i < N; i++)
{
if(match[i] == -1)
{
memset(vis,false,sizeof(vis));
augment(i);
}
}
for(int i = 0; i < N; i++)
{
if(inv[i] == -1)ans++;
}
cout << ans << endl;
}
return 0;
}
Java Problem solving HackerRank Solution
import java.io.*;
import java.util.*;
public class Solution {
private void solution() throws IOException {
int ts = in.nextInt();
while (ts-- > 0) {
int n = in.nextInt();
int k = in.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = in.nextInt();
}
int size = 2 * n + 2;
int[][] cap = new int[size][size];
int[][] flow = new int[size][size];
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (Math.abs(a[i] - a[j]) >= k) {
cap[i][n + j] = 1;
}
}
}
int s = size - 2;
int t = size - 1;
for (int i = 0; i < n; ++i) {
cap[s][i] = 1;
cap[n + i][t] = 1;
}
boolean[] used = new boolean[size];
int res = 0;
while (dfs(s, t, cap, flow, used)) {
++res;
Arrays.fill(used, false);
}
out.println(n - res);
}
}
private boolean dfs(int at, int t, int[][] cap, int[][] flow, boolean[] used) {
if (used[at]) {
return false;
}
if (at == t) {
return true;
}
used[at] = true;
for (int next = 0; next < cap.length; ++next) {
if (!used[next] && cap[at][next] > flow[at][next]) {
if (dfs(next, t, cap, flow, used)) {
++flow[at][next];
--flow[next][at];
return true;
}
}
}
return false;
}
public void run() {
try {
solution();
in.reader.close();
out.close();
} catch (Exception e) {
e.printStackTrace();
System.exit(1);
}
}
private class Scanner {
StringTokenizer tokenizer;
BufferedReader reader;
public Scanner(Reader reader) {
this.reader = new BufferedReader(reader);
this.tokenizer = new StringTokenizer("");
}
public boolean hasNext() throws IOException {
while (!tokenizer.hasMoreTokens()) {
String line = reader.readLine();
if (line == null) {
return false;
}
tokenizer = new StringTokenizer(line);
}
return true;
}
public String next() throws IOException {
hasNext();
return tokenizer.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
}
public static void main(String[] args) throws IOException {
new Solution().run();
}
Scanner in = new Scanner(new InputStreamReader(System.in));
PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
}
Python 3 Problem solving HackerRank Solution
T = int(input())
for _ in range(T):
N, K = map(int, input().split())
vi = list(map(int, input().split()))
m = [None] * N
def match(s):
if v[s]: return False
v[s] = True
for i in range(s+1, N):
if abs(vi[i] - vi[s]) < K: continue
if m[i] == None or match(m[i]):
m[i] = s
return True
return False
mc = 0
for i in range(N):
v = [False] * N
if match(i): mc += 1
print(N - mc)
Python 2 Problem solving HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
from itertools import chain
def tr(G):
GT = {}
for u in G: GT[u] = set()
for u in G:
for v in G[u]:
GT[v].add(u)
return GT
def order(k, probs):
G = {}
for u in range(len(probs)):
G[str(u)] = set()
G[str(u)+'*']= set()
for i in range(len(probs)):
for j in range(i+1,len(probs)):
if (probs[i]-probs[j])**2 >= k*k:
G[str(i)].add(str(j)+'*')
Left = {str(v) for v in range(len(probs))}
Right = {str(v)+'*' for v in range(len(probs))}
Gp = tr(G)
M = set()
while Left:
s = Left.pop()
Q, P = {s}, {}
while Q:
u = Q.pop()
if u in Right:
Right.remove(u)
break
ahead = (v for v in G[u] if (u,v) not in M)
back = (v for v in Gp[u] if (v,u) in M)
for v in chain(ahead,back):
if v in P: continue
P[v] = u
Q.add(v)
while u != s:
u, v = P[u], u
if v in G[u]:
M.add((u,v))
else:
M.remove((v,u))
return len(M)
if __name__ == '__main__':
str0 = sys.stdin.readline().split()
nums = int(str0[0])
cases = []
for i in range(nums):
str1 = sys.stdin.readline().split()
k = int(str1[1])
str2 = sys.stdin.readline().split()
probs = [int(val) for val in str2]
cases.append([k,probs])
for case in cases:
print len(case[1])- order(case[0],case[1])
C Problem solving HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#define MAXPROBLEM 300
int problem[MAXPROBLEM];
bool completed[MAXPROBLEM];
bool path[MAXPROBLEM][MAXPROBLEM];
bool visited[MAXPROBLEM];
int prev[MAXPROBLEM];
int numProblems;
bool findNextDfs(int curProblem) {
if(curProblem == -1)
return true;
if(visited[curProblem])
return false;
visited[curProblem]=true;
for (int i = 0; i< numProblems; i++)
if(path[curProblem][i])
if(findNextDfs(prev[i])) {
prev[i]=curProblem;
return true;
}
return false;
}
int main() {
int numCases, minDiff;
scanf ("%d\n", &numCases);
for (int i = 0; i < numCases; i++) {
scanf ("%d %d\n", &numProblems, &minDiff);
for (int j = 0; j < numProblems; j++) {
scanf ("%d\n", &problem[j]);
completed[j] = false;
}
memset(path, false, sizeof(path));
for (int j = 0; j < numProblems; j++)
for (int k = j + 1; k < numProblems; k++)
if (abs(problem[j] - problem[k]) >= minDiff)
path[j][k] = true;
int numDays = 0;
memset(prev, -1, sizeof(prev));
for (int j = 0; j < numProblems; j++) {
memset(visited, false, sizeof(visited));
if (!findNextDfs(j))
numDays++;
}
printf ("%d\n", numDays);
}
return 0;
}
Leave a comment below
