Table of Contents
Requirement – 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++ Requirement HackerRank Solution
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <fstream>
#include <numeric>
#include <iomanip>
#include <bitset>
#include <list>
#include <stdexcept>
#include <functional>
#include <utility>
#include <ctime>
#include <complex>
using namespace std;
// begin insert defines
#define two(x) (1LL<<(x))
#define forE(elem,v) for(__typeof__(v.begin()) _it = v.begin(); _it != v.end();++_it) for(int _once=1, _done=0; _once; (!_done) ? (_it=v.end(), --_it) :_it ) for(__typeof__(*_it) & elem = * _it; _once && !(_once=0); _done=1)
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)
// end insert defines
const int N = 13, B = 1 << 13, M = 1007, L = 10;
vector<int> lnk[N];
int ls[B], f[L][B];
void madd(int &a, int b)
{
a += b;
if (a >= M) a -= M;
}
int dp(int lv, int s)
{
if (lv >= 10) return !s;
int &ret = f[lv][s];
if (ret != -1) return ret;
ret = 0;
for (int subset = s; subset > 0; subset = (subset - 1) & s) {
if (!(ls[subset] & (~s))) {
madd(ret, dp(lv + 1, s ^ subset));
}
}
madd(ret, dp(lv + 1, s));
return ret;
}
int n, m;
int main(int argc, char *argv[])
{
cin >> n >> m;
Rep(i, n) lnk[i].clear();
Rep(i, m) {
int x, y;
cin >> x >> y;
lnk[x].push_back(y);
}
Rep(i, two(n)) {
ls[i] = 0;
Rep(j, n) if (two(j) & i) forE(v, lnk[j]) ls[i] |= two(v);
}
memset(f, -1, sizeof(f));
cout << dp(0, two(n) - 1) << endl;
return 0;
}
Java Requirement HackerRank Solution
import java.util.*;
import static java.lang.Math.*;
import java.io.*;
public class Solution {
static class Foo41 {
final static int MOD = 1007;
int N;
int highLen;
int lowLen;
int[] topsort;
int[] reverseTopsort;
Graph highReverse;
Graph lowReverse;
Graph crossGraph;
MultiArray[] dp;
int res = 0;
void main() {
BufferedReader br = null;
try {
br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split("\\s");
int N = Integer.parseInt(s[0]);
int M = Integer.parseInt(s[1]);
TreeSet<Integer>[] g = new TreeSet[N];
for (int i = 0; i < N; i++)
g[i] = new TreeSet<Integer>();
for (int i = 1; i <= M; i++) {
s = br.readLine().split("\\s");
int x = Integer.parseInt(s[0]);
int y = Integer.parseInt(s[1]);
if (x != y)
g[y].add(x);
}
Graph graph = new Graph();
graph.n = N;
graph.degree = new int[N];
graph.graph = new int[N][N];
for (int u = 0; u < N; u++) {
for (int v : g[u]) {
graph.graph[u][graph.degree[u]++] = v;
}
}
//long t = System.currentTimeMillis();
int res = foo(graph);
//System.out.println(System.currentTimeMillis()-t);
System.out.println(res);
} catch (Exception e) {
e.printStackTrace();
} finally {
try {
br.close();
} catch (Exception e) {
e.printStackTrace();
}
}
}
int foo(Graph g) {
g = new TarjanSCC().doit(g);
topsort = topsort(g);
N = topsort.length;
highLen = (N+1)/2;
lowLen = N - highLen;
reverseTopsort = reverse(topsort);
highReverse = highReverse(g);
lowReverse = lowReverse(g);
crossGraph = crossGraph(g);
dp = new MultiArray[highLen+1];
for (int i = 0; i <= highLen; i++) {
dp[i] = new MultiArray(i);
}
for (int i = 1; i <= highLen; i++) {
fillMultiArray(i);
}
int[] arr = new int[N];
//int[] util = new int[N];
sumAll(arr);
return res;
}
void sumAll(int[] arr) {
sumAll(arr, highLen);
}
void sumAll(int[] arr, int index) {
if (index == N) {
for (int i = 0; i < highLen; i++) {
arr[i] = 0;
int u = topsort[i];
for (int j = 0; j < crossGraph.degree[u]; j++) {
int v = crossGraph.graph[u][j];
arr[i] = max(arr[i], arr[reverseTopsort[v]]);
}
}
//System.out.println(Arrays.toString(Arrays.copyOfRange(arr, highLen, N)) + ": " + dp[highLen].get(arr, highLen));
res = (res + dp[highLen].get(arr, highLen)) % MOD;
return;
}
int ceiling = 9;
int u = topsort[index];
for (int j = 0; j < lowReverse.degree[u]; j++) {
int v = lowReverse.graph[u][j];
ceiling = min(ceiling, arr[reverseTopsort[v]]);
}
for (int i = ceiling; i >= 0; i--) {
arr[index] = i;
sumAll(arr, index+1);
}
}
void fillMultiArray(int len) {
int[] arr = new int[len];
int[] util = new int[len];
for (int i = 9; i >= 0; i--) {
arr[len-1] = i;
fill(arr, util, 0, len);
}
}
void fill(int[] arr, int[] util, int index, int len) {
if (index == len-1) {
int res = 0;
copyArray(arr, util, len);
int u = topsort[len-1];
for (int j = 0; j < highReverse.degree[u]; j++) {
int v = highReverse.graph[u][j];
util[reverseTopsort[v]] = max(util[reverseTopsort[v]], util[len-1]);
}
res = dp[len-1].get(util, len-1);
if (util[len-1] < 9) {
util[len-1]++;
for (int j = 0; j < highReverse.degree[u]; j++) {
int v = highReverse.graph[u][j];
util[reverseTopsort[v]] = max(util[reverseTopsort[v]], util[len-1]);
}
res = (res + dp[len].get(util, len)) % MOD;
}
dp[len].set(arr, len, res);
return;
}
for (int i = 9; i >= 0; i--) {
arr[index] = i;
fill(arr, util, index+1, len);
}
}
void copyArray(int[] a, int[] b, int n) {
for (int i = 0; i < n; i++)
b[i] = a[i];
}
Graph highReverse(Graph g) {
Graph graph = new Graph();
int n = g.n;
graph.n = n;
graph.degree = new int[n];
graph.graph = new int[n][n];
for (int i = 0; i < highLen; i++) {
int u = topsort[i];
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
if (reverseTopsort[v] < highLen)
graph.graph[v][graph.degree[v]++] = u;
}
}
return graph;
}
Graph lowReverse(Graph g) {
Graph graph = new Graph();
int n = g.n;
graph.n = n;
graph.degree = new int[n];
graph.graph = new int[n][n];
for (int i = highLen; i < N; i++) {
int u = topsort[i];
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
if (reverseTopsort[v] >= highLen)
graph.graph[v][graph.degree[v]++] = u;
}
}
return graph;
}
Graph crossGraph(Graph g) {
Graph graph = new Graph();
int n = g.n;
graph.n = n;
graph.degree = new int[n];
graph.graph = new int[n][n];
for (int i = 0; i < highLen; i++) {
int u = topsort[i];
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
if (reverseTopsort[v] >= highLen)
graph.graph[u][graph.degree[u]++] = v;
}
}
return graph;
}
int[] reverse(int[] arr) {
int n = arr.length;
int[] res = new int[n];
for (int i = 0; i < n; i++)
res[arr[i]] = i;
return res;
}
static class Graph {
int n;
int[][] graph;
int[] degree;
}
int[] topsort(Graph g) {
int n = g.n;
int[] res = new int[n];
int count = 0;
Queue<Integer> queue = new ArrayDeque<Integer>();
int[] indegree = new int[n];
for (int u = 0; u < n; u++) {
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
indegree[v]++;
}
}
for (int u = 0; u < n; u++) {
if (indegree[u] == 0)
queue.add(u);
}
while (!queue.isEmpty()) {
int u = queue.remove();
res[count++] = u;
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
if (--indegree[v] == 0)
queue.add(v);
}
}
return res;
}
static class MultiArray {
final static int LEN = 10;
int[] val;
MultiArray[] array;
public MultiArray(int m) {
if (m == 0)
return;
if (m == 1) {
val = new int[LEN];
Arrays.fill(val, -1);
} else {
array = new MultiArray[LEN];
for (int i = 0; i < LEN; i++)
array[i] = new MultiArray(m-1);
}
}
// the first n elem of arr are indexes
int get(int[] arr, int n) {
if (n == 0)
return 1;
return get(this, arr, 0, n);
}
int get(MultiArray m, int[] arr, int index, int n) {
if (index == n-1) {
return m.val[arr[index]];
}
return get(m.array[arr[index]], arr, index+1, n);
}
void set(int[] arr, int n, int val) {
set(this, arr, 0, n, val);
}
void set(MultiArray m, int[] arr, int index, int n, int val) {
if (index == n-1) {
m.val[arr[index]] = val;
return;
}
set(m.array[arr[index]], arr, index+1, n, val);
}
}
static class TarjanSCC {
int n;
int ind;
int[] index;
int[] lowIndex;
Deque<Integer> stack;
boolean[] inStack;
int comp;
int[] component;
Graph g;
Graph doit(Graph g) {
this.g = g;
n = g.n;
index = new int[n];
Arrays.fill(index, -1);
lowIndex = new int[n];
stack = new LinkedList<Integer>();
inStack = new boolean[n];
component = new int[n];
for (int u = 0; u < n; u++) {
if (index[u] == -1)
tarjan(u);
}
TreeSet<Integer>[] newGraph = new TreeSet[comp];
for (int i = 0; i < comp; i++)
newGraph[i] = new TreeSet<Integer>();
for (int u = 0; u < n; u++) {
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
if (component[u] != component[v])
newGraph[component[u]].add(component[v]);
}
}
Graph graph = new Graph();
graph.n = comp;
graph.degree = new int[n];
graph.graph = new int[n][n];
for (int u = 0; u < comp; u++) {
for (int v : newGraph[u]) {
graph.graph[u][graph.degree[u]++] = v;
}
}
return graph;
}
void tarjan(int u) {
index[u] = ind;
lowIndex[u] = ind;
ind++;
stack.push(u);
inStack[u] = true;
for (int j = 0; j < g.degree[u]; j++) {
int v = g.graph[u][j];
if (index[v] == -1) {
tarjan(v);
lowIndex[u] = min(lowIndex[u], lowIndex[v]);
} else if (inStack[v]) {
lowIndex[u] = min(lowIndex[u], index[v]);
}
}
if (index[u] == lowIndex[u]) {
int w = 0;
do {
w = stack.pop();
inStack[w] = false;
component[w] = comp;
} while (u != w);
comp++;
}
}
}
}
public static void main(String[] args) {
Foo41 foo = new Foo41();
foo.main();
}
}
Python 3 Requirement HackerRank Solution
import sys
n = 6 # between 0-9
maxn = 10
reqs = [(0,1), (1,2)]
reqs3 = [(1,3), (1,2)]
reqs2 = [(1,3), (0,1), (2,4),(0,4), (2,5),(3,4),(0,2)]
## how many different assignments (modulo by 1007)
def match_reqs(acc_list, reqs):
for a,b in reqs:
if acc_list[a] > acc_list[b]:
return False
return True
def req(n, reqs, acc_list):
print(n, reqs, acc_list)
summ = 0
if (n == 0):
if match_reqs(acc_list, reqs):
return 1
else:
return 0
for i in range(maxn):
summ += req(n-1, reqs, acc_list + [i])
# return summ % 1007
return summ
def req2(n, reqs):
if (n == 0):
assert(reqs == [])
return list(map(lambda x: [x], range(maxn)))
reqs1, reqs2 = split_reqs(reqs, n)
solutions = []
subsolutions = req2(n-1, reqs1)
print(n, len(subsolutions))
print("FUCK YOU")
for i in range(maxn):
solutions += filter_list(subsolutions, i, reqs2)
return solutions
def req22(n, reqs):
return len(req2(n - 1, reqs)) % 1007
def split_reqs(reqs, n):
reqs1 = []
reqs2 = []
for a,b in reqs:
if a == n or b == n:
reqs2.append((a,b))
else:
reqs1.append((a,b))
return reqs1, reqs2
def filter_list(solutions, newval, reqs):
result = []
for solution in solutions:
if match_reqs(solution + [newval], reqs):
result.append(solution + [newval])
return result
from operator import mul
from functools import reduce
def rlen(r):
a,b = r
if a > b:
return 0
return b-a+1
def update_ranges(ranges, val, reqs):
removed_var = len(ranges)
updated = list(ranges)
for a,b in reqs:
if a == removed_var:
x, y = updated[b]
if val > x:
updated[b] = (val, y)
if b == removed_var:
x, y = updated[a]
if val < y:
updated[a] = (x, val)
return updated
memodict = {}
def req3(ranges, reqs):
if (reqs == []):
return reduce(mul, map(rlen, ranges), 1)
key = (tuple(ranges),tuple(reqs))
if key in memodict:
return memodict[key]
summ = 0
lastr = ranges[-1]
rest = ranges[:-1]
a,b = lastr
unrelated, related = split_reqs(reqs, len(rest))
for val in range(a,b+1):
updated = update_ranges(rest, val, related)
summ += req3(updated, unrelated)
summ = summ % 1007
memodict[key] = summ
return summ
def req33(n, reqs):
return req3([(0, maxn-1)] * n, reqs) % 1007
#print(req(n, reqs2, []) % 1007)
def runcommand():
req_list = []
n,m = map(int, sys.stdin.readline().split())
for _ in range(m):
a,b = map(int, sys.stdin.readline().split())
req_list.append((a,b))
print(req33(n, req_list))
runcommand()
#print(req22(6, reqs2))
#print(req33(6, reqs2))
Python 2 Requirement HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
#!/usr/bin/python
import itertools
import operator
def memo(f):
save = {}
def func(*args):
if args in save:
return save[args]
ret = f(*args)
save[args] = ret
return ret
return func
getnums = lambda: map(int, raw_input().strip().split())
n, m = getnums()
le = [ [ x == y for x in xrange(n) ] for y in xrange(n) ]
#print le
for x in xrange(m):
a, b = getnums()
le[a][b] = 1
for k in xrange(n):
for i in xrange(n):
for j in xrange(n):
le[i][j] |= le[i][k] & le[k][j]
#print le
@memo
def subsets(nums):
if len(nums) == 0: return []
a = 1<<nums[0]
ret = [a]
for x in subsets(nums[1:]):
ret.append(x)
ret.append(a|x)
return ret
#print subsets((0,1,2))
@memo
def ok(mask, now):
if mask & (1<<now): return False
for x in xrange(n):
if mask & (1 << x) and le[now][x]:
return False
return True
dst = (1 << n) - 1
#print bin(dst)
@memo
def f(mask, lastval):
ret = 0
if mask == dst: return 1
candidates = tuple(x for x in xrange(n) if ok(mask, x))
for x in subsets(candidates):
#print 'chosen', bin(x)
for val in xrange(lastval+1, 10):
ret = (ret + f(mask | x, val)) % 1007
#print bin(mask), lastval, ret
return ret
print f(0, -1)
C Requirement HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
long long v[100000],b[20][20],i,j,k,l,m,n,a[20000][16];
long long bin[100][100];
void makaj(long long ii, long long horna, long long ind)
{
while(ind<n && (ii&(1<<ind))==0) ind++;
if(ind ==n)
{
//koncim
long long jj,kk,ll;
jj = (ii^horna);
if(horna==0) return;
// printf("ii=%lld horna=%lld jj=%lld\n",ii,horna,jj);
if(v[horna]==0 || v[jj]==0) return;
for(kk=0;kk<n;kk++)
if((1<<kk)&horna)
for(ll=0;ll<n;ll++)
if(((1<<ll)&jj) && b[ll][kk]) return;
for(kk=1;kk<=10;kk++)
{
a[ii][kk] += a[jj][kk-1];
// printf("ii=%lld kk=%lld jj=%lld pridavam %lld\n",ii,kk,jj,a[jj][kk-1]);
}
return;
}
makaj(ii, horna, ind+1);
makaj(ii, horna + (1<<ind), ind+1);
return ;
}
int main()
{
for(i=0;i<20;i++) bin[i][0] = bin[i][i] = 1;
for(i=1;i<=20;i++)
for(j=1;j<i;j++)
bin[i][j] = bin[i-1][j-1] + bin[i-1][j];
scanf("%lld %lld",&n,&m);
while(m--) {scanf("%lld %lld",&i,&j);b[j][i]=1;}
for(m=0;m<n+2;m++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(b[i][j])
for(k=0;k<n;k++)
if(b[j][k]) b[i][k] = 1;
/*
for(i=0;i<n;i++)
{
printf("%lld:",i);
for(j=0;j<n;j++) printf("%lld ",b[i][j]);
printf("\n");
}
*/
for(i=0;i<(1<<n);i++)
{
v[i]=1;
for(j=0;j<n;j++)
if(i&(1<<j))
for(k=0;k<n;k++)
if(i&(1<<k))
for(l=0;l<n;l++)
if((i&(1<<l))==0 && b[j][l] && b[l][k]) {
//printf("%lld hmm\n",i);
v[i]=0;
}
// if(v[i]) printf("%lld\n",i);
}
a[0][0]=1;
for(i=1;i<(1<<n);i++)
//for(i=1;i<=2;i++)
if(v[i])
{
// j=0;/
// while(((1<<j)&i)==0) j++;
// printf("makaj %lld %lld=j %lld\n",i,j,1<<j);
makaj(i,0,0);
}
m=0;
//printf("bin %lld\n",bin[10][1]);
for(i=0;i<=10;i++)
{
m+=a[(1<<n)-1][i]*bin[10][i];
// printf("%lld %lld\n",i, a[(1<<n)-1][i]*bin[10][i]);
}
//for(j=0;j<(1<<n);j++)
//for(i=0;i<=10;i++)
// printf("%lld=i %lld=far pocet=%lld\n",j,i,a[(1<<n)-1][i]);
printf("%lld\n",m%1007);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
