# HackerRank Requirement problem solution

In this HackerRank Requirement problem solution, There are N variables and M requirements. Requirements are represented as (x <= y), meaning that the Xth variable must be less than or equal to the Yth variable.

Your task is to assign non-negative numbers smaller than 10 to each variable and then calculate the number of different assignments satisfying all requirements. Two assignments are different if and only if at least one variable is assigned to a different number in both assignments. Print your answer modulo 10 to power 3 plus 7.

## Problem solution in Java.

```import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

static int n = 15;
static Map<Integer, Map<Long, Long>> memoMap = new HashMap<Integer, Map<Long, Long>>();

static {
for(int v = 0;v <= n;v++) {
memoMap.put(v, new  HashMap<Long, Long>());
}
}

static long calcR(int[] vals, int k) {
int[] maxV = calcFK(vals, k);
long key = 0;
for(int mv : maxV) {
key = key * 10+mv;
}
Long ans = memoMap.get(k).get(key);
if(ans != null) {
return ans;
}
if(k == n-1) {
ans = maxV[0]+1l;
memoMap.get(k).put(key, ans);
return ans;
}else {
ans = 0l;
for(int v = maxV[0];v >= 0;v--) {
vals[k] = v;
ans += calcR(vals, k+1);
}
memoMap.get(k).put(key, ans);
return ans;
}
}

static private int[] calcFK(int[] vals, int k) {
int[] ans = new int[n-k];
for(int i = 0;i < n-k;i++) {
ans[i] = 9;
}
for(int i = 0;i < k;i++) {
int mv = vals[i];
for(int j = 0;j < np.length;j++) {
int npAV = np[j];
if(npAV >= k) {
int val = ans[npAV-k];
if(val > mv) {
ans[npAV-k] = mv;
}
}
}
}
return ans;
}

static class Node{

int v;
int index;

int color = 0;
int startT = 0;
int endT = 0;

public Node(int v) {
this.v = v;
}
}

static long requirement(int[][] req) {
int m = req.length;
Node[] nodes = new Node[n];
for(int i = 0; i < n;i++) {
nodes[i] = new Node(i);
}
for(int i = 0; i < m;i++) {
int to = req[i][0];
int from = req[i][1];
}
process(nodes);
return  calcR(new int[n], 0);
}

private static void process(Node[] nodes) {
DFS(nodes);
for(int i = 0;i < n;i++) {
nodes[i].color = 0;
}
List<Node> tSL2 = tSL;
for(int i = 0;i < n;i++) {
Node node = tSL2.get(i);
if(node.color == 0) {
Set<Node> set = new HashSet<Node>();
DFS_VISIT(set, nodes, node, true);

}
}
int k = 0;
for(int i = 0;i < listSCC.size();i++) {
Set<Integer> set = new HashSet<Integer>();
Set<Node> cc = listSCC.get(i);
for(Node node : cc) {
node.index = k;
}
k++;
}
for(int i = 0;i < listSCC.size();i++) {
Set<Integer> set = new HashSet<Integer>();
Set<Node> cc = listSCC.get(i);
for(Node node : cc) {
if(na.index != node.index) {
}
}
}
int p = 0;
for(int a : set) {
}
}
n = k;
}

static int time = 0;

private static void DFS(Node[] nodes) {
for(int i = 0;i < n;i++) {
Node node = nodes[i];
if(node.color == 0) {
Set<Node> set = new HashSet<Node>();
DFS_VISIT(set, nodes, nodes[i], false);
}
}
}

private static void DFS_VISIT(Set<Node> set, Node[] nodes, Node u, boolean transposeG) {
time++;
u.startT = time;
u.color = 1;
if(v.color == 0) {
//v.parent = u;
DFS_VISIT(set, nodes, v, transposeG);
}
}
u.color = 2;
time++;
u.endT = time;
}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] nm = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
n = Integer.parseInt(nm[0]);
int m = Integer.parseInt(nm[1]);
int[][] req = new int[m][2];
for (int reqRowItr = 0; reqRowItr < m; reqRowItr++) {
String[] reqRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

for (int reqColumnItr = 0; reqColumnItr < 2; reqColumnItr++) {
int reqItem = Integer.parseInt(reqRowItems[reqColumnItr]);
req[reqRowItr][reqColumnItr] = reqItem;
}
}
long result = requirement(req);
bufferedWriter.write(String.valueOf(result % 1007));
bufferedWriter.newLine();
bufferedWriter.close();
scanner.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <bits/stdc++.h>
using namespace std;
#define M 10000010
const int mod = 1e3 + 7;

int flag[M], po[20], ans, a[20], b[20], n, Q, m, sum;

inline void chv(int &x, int y) {x += y; if (x >= mod) x -= mod;}

vector <int> v[20], vs[20], vb[20];

short g[8][M];

void init() {
for (int i = 0; i < po[n - m]; i++) g[n - m][i] = flag[i];
for (int i = n - m - 1; i >= 0; i--) {
for (int j = po[n - m] - 1; j >= 0; j--) {
int u = (j / po[i]) % 10;
g[i][j] = g[i + 1][j];
if (u < 9) {
g[i][j] += g[i][j + po[i]];
if (g[i][j] >= mod) g[i][j] -= mod;
}
}
}
}

int main() {
//freopen("in.txt", "r", stdin);
scanf("%d %d", &n, &Q);

po[0] = 1; for (int i = 1; i < 9; i++) po[i] = po[i - 1] * 10;
int x, y;

m = n / 2;
while (Q--) {
scanf("%d %d", &x, &y);
v[x].push_back(y);
if (x < m && y < m) vs[x].push_back(y);
else if (x >= m && y >= m) vb[x-m].push_back(y-m);
}

for (int i = 0; i < po[n - m]; i++) {
x = i;
int bf = 1;
for (int j = 0; j < n - m; j++) a[j] = x % 10, x /= 10;
for (int j = 0; j < n - m; j++) {
for (int k = 0; k < vb[j].size(); k++) {
int u = vb[j][k];
if (a[u] < a[j]) {
bf = 0; break;
}
}
if (!bf) break;
}
flag[i] = bf;
}

init();

for (int i = 0; i < po[m]; i++) {
x = i;
int bf = 1;
for (int j = 0; j < m; j++) a[j] = x % 10, x /= 10;
for (int j = 0; j < m; j++) {
for (int k = 0; k < vs[j].size(); k++) {
int u = vs[j][k];
if (a[u] < a[j]) {
bf = 0; break;
}
}
if (!bf) break;
}
if (bf) {
int rt = 0;
for (int j = 0; j < n - m; j++) b[j] = 0;
for (int j = 0; j < m; j++) {
for (int k = 0; k < v[j].size(); k++) {
int u = v[j][k]; if (u < m) continue;
b[u-m] = max(b[u-m], a[j]);
}
}
for (int j = 0; j < n - m; j++) rt += po[j] * b[j];
chv(ans, g[0][rt]);
}
}
printf("%d\n", ans);
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
#define INF 9999
#define MOD 1007
typedef struct _list{
struct _list *next;
} list;
int table[13][13],dp1[13][13][14],dp3[9000][10];
list *dp2[9000];
int min(int x,int y);

int main(){
int n,m,x,y,i,j,k;
list *t,*cur;
for(i=0;i<13;i++)
for(j=0;j<13;j++)
table[i][j]=INF;
scanf("%d%d",&n,&m);
for(i=0;i<m;i++){
scanf("%d%d",&x,&y);
if(x!=y)
table[x][y]=-1;
}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dp1[i][j][0]=table[i][j];
for(k=1;k<=n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dp1[i][j][k]=min(dp1[i][j][k-1],dp1[i][k-1][k-1]+dp1[k-1][j][k-1]);
t=(list*)malloc(sizeof(list));
t->next=NULL;
dp2[0]=t;
for(i=1;i<(1<<n);i++){
x=findleft(i,n);
dp2[i]=dp2[i^(1<<x)];
cur=dp2[i^x];
while(cur){
t=(list*)malloc(sizeof(list));
t->next=dp2[i];
dp2[i]=t;
cur=cur->next;
}
}
for(i=0;i<(1<<n);i++)
dp3[i][0]=1;
for(i=1;i<10;i++)
for(j=0;j<(1<<n);j++){
dp3[j][i]=0;
cur=dp2[j];
while(cur){
cur=cur->next;
}
}
printf("%d",dp3[(1<<n)-1][9]);
return 0;
}
int min(int x,int y){
return (x>y)?y:x;
}
int i,j,flag;
for(i=0;i<n;i++)
flag=0;
for(j=0;j<n;j++)
if(dp1[j][i][n]<0){
flag=1;
break;
}
if(!flag)
return i;
}
return i;
}