Table of Contents
Demanding Money – 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++ Demanding Money HackerRank Solution
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<pii> vii;
typedef vector<string> vs;
vvi g;
vi deg, used, c;
int ma = -1;
ll cnt = 0;
int sum = 0, c0 = 0;
void rec(int v) {
if (v >= g.size()) {
if (sum > ma) {
ma = sum;
cnt = 0;
}
if (sum == ma) {
cnt += (1LL << c0);
}
return;
}
if (!used[v]) {
sum += c[v];
bool alone = 1;
for (int nv : g[v]) {
if (!used[nv]) {
alone = false;
}
++used[nv];
}
if (alone && c[v] == 0) ++c0;
rec(v + 1);
sum -= c[v];
if (alone && c[v] == 0) --c0;
for (int nv : g[v]) {
--used[nv];
}
if (!alone) rec(v + 1);
} else {
rec(v + 1);
}
}
int main() {
int n, m;
cin >> n >> m;
c.resize(n);
for (int i = 0; i < n; ++i) cin >> c[i];
g.resize(n);
deg.assign(n, 0);
used.assign(n, 0);
for (int i = 0; i < m; ++i) {
int a,b;
cin >> a >> b;
if (a > b) swap(a, b);
--a; --b;
g[a].push_back(b);
//g[b].push_back(a);
++deg[a]; ++deg[b];
}
rec(0);
cout << ma << ' ' << cnt << endl;
return 0;
}
Java Demanding Money HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class D2 {
InputStream is;
PrintWriter out;
String INPUT = "";
void solve()
{
int n = ni(), m = ni();
int[] a = na(n);
long[] g = new long[n];
for(int i = 0;i < m;i++){
int f = ni()-1, t = ni()-1;
g[f] |= 1L<<t;
g[t] |= 1L<<f;
}
for(int i = 0;i < n;i++){
g[i] |= 1L<<i;
}
int h = n/2;
int[] suml = new int[1<<h];
boolean[] okl = new boolean[1<<h];
okl[0] = true;
for(int i = 1;i < 1<<h;i++){
int j = Integer.numberOfTrailingZeros(i);
suml[i] = suml[i^1<<j] + a[j];
okl[i] = okl[i^1<<j] && (g[j]&(i^1<<j)) == 0;
}
int[] sumh = new int[1<<n-h];
boolean[] okh = new boolean[1<<n-h];
okh[0] = true;
for(int i = 1;i < 1<<n-h;i++){
int j = Integer.numberOfTrailingZeros(i);
sumh[i] = sumh[i^1<<j] + a[j+h];
okh[i] = okh[i^1<<j] && ((g[j+h]>>>h)&(i^1<<j)) == 0;
}
long[] counth = new long[1<<n-h];
for(int i = 0;i < 1<<n-h;i++){
if(okh[i]){
counth[i] = 1;
}else{
sumh[i] = -1;
}
}
for(int j = 0;j < n-h;j++){
for(int i = 0;i < 1<<n-h;i++){
if(i<<~j>=0){
int ni = i^1<<j;
if(sumh[i] > sumh[ni]){
sumh[ni] = sumh[i];
counth[ni] = counth[i];
}else if(sumh[i] == sumh[ni]){
counth[ni] += counth[i];
}
}
}
}
long maxsum = -1;
long count = 0;
for(int i = 0;i < 1<<h;i++){
if(!okl[i])continue;
long merge = 0;
for(int j = 0;j < h;j++){
if(i<<~j<0){
merge |= g[j];
}
}
int rem = (int)(((1L<<n)-1^merge)>>>h);
if(sumh[rem] != -1){
long s = sumh[rem] + suml[i];
if(s > maxsum){
maxsum = s;
count = counth[rem];
}else if(s == maxsum){
count += counth[rem];
}
}
}
out.println(maxsum + " " + count);
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new D2().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
Python 3 Demanding Money HackerRank Solution
def solve(C,G) :
minLost = {}
def getMinLost(housesToVisit) :
# print("getMinLost %s :" % str(housesToVisit))
if not housesToVisit :
return 0,1
key = frozenset(housesToVisit)
if key in minLost :
return minLost[key]
a = housesToVisit.pop()
# Do not visit house a
lost, nb = getMinLost(housesToVisit)
lost += C[a]
# Visit house a
lostHouses = set(b for b in G[a] if b in housesToVisit)
lostMoney = sum(C[b] for b in lostHouses)
losta, nba = getMinLost(housesToVisit - lostHouses)
losta += lostMoney
housesToVisit.add(a)
if losta < lost :
lost, nb = losta, nba
elif losta == lost :
nb += nba
minLost[key] = (lost,nb)
return minLost[key]
amount, number = getMinLost(set(range(len(C))))
return sum(C)-amount, number
N,M = map(int,input().split())
C = tuple(map(int,input().split()))
G = {a : set() for a in range(len(C))}
for _ in range(M) :
a,b = map(int,input().split())
G[a-1].add(b-1)
G[b-1].add(a-1)
print(" ".join(map(str,solve(C,G))))
Python 2 Demanding Money HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
c=list(map(int,input().split()))
g=[[] for _ in range(n)]
for _ in range(m):
u,v=map(int,input().split())
g[u-1].append(v-1)
g[v-1].append(u-1)
# visit each connected component
a1=0
a2=1
vis=[0]*n
col=[0]*n # temp colouring, 0 = not pick, 1 = pick
l1=[]
l2=[]
def getinfo(idx):
# base case
if idx==len(l1):
# count
out=0
for i in l1:
if col[i]:
out+=c[i]
return (out,1)
# general case
for i in g[l1[idx]]:
if col[i]:
# cannot rob
return getinfo(idx+1)
# choice of robbing
p1,p2=getinfo(idx+1)
col[l1[idx]]=1
q1,q2=getinfo(idx+1)
col[l1[idx]]=0
if p1==q1:
return (p1,p2+q2)
return max((p1,p2),(q1,q2))
for i in range(n):
if not vis[i]:
# dfs that is horrible to code
l1=[i]
l2=[i]
vis[i]=1
while l2:
u=l2.pop(-1)
for v in g[u]:
if not vis[v]:
l1.append(v)
l2.append(v)
vis[v]=1
# get money info
b1,b2=getinfo(0)
a1+=b1
a2*=b2
# print
print("%s %s"%(a1,a2))
C Demanding Money HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 123455
typedef struct _node{
long long x;
int aa;
long long bb;
struct _node *next;
} node;
void insert_edge(int x,int y,int w);
void insert(long long x,int aa,long long bb);
int search(long long x,int *aa,long long *bb);
void solve(long long x,int *aa,long long *bb);
int a[34],N;
long long link[34]={0};
node *hash[HASH_SIZE]={0};
int main(){
int M,x,y,i;
long long ans;
scanf("%d%d",&N,&M);
for(i=0;i<N;i++)
scanf("%d",a+i);
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
solve((1LL<<N)-1,&x,&ans);
printf("%d %lld",x,ans);
return 0;
}
void insert_edge(int x,int y,int w){
link[x]|=(1LL<<y);
link[y]|=(1LL<<x);
return;
}
void insert(long long x,int aa,long long bb){
int bucket=x%HASH_SIZE;
node *t=hash[bucket];
t=(node*)malloc(sizeof(node));
t->x=x;
t->aa=aa;
t->bb=bb;
t->next=hash[bucket];
hash[bucket]=t;
return;
}
int search(long long x,int *aa,long long *bb){
int bucket=x%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->x==x){
*aa=t->aa;
*bb=t->bb;
return 1;
}
t=t->next;
}
return 0;
}
void solve(long long x,int *aa,long long *bb){
int aa1,aa2,i;
long long bb1,bb2;
if(!x){
*aa=0;
*bb=1;
return;
}
if(search(x,aa,bb))
return;
for(i=0;i<N;i++)
if((1LL<<i)&x)
break;
solve(x&(~(1LL<<i)),&aa1,&bb1);
solve(x&(~link[i])&(~(1LL<<i)),&aa2,&bb2);
aa2+=a[i];
if(aa1==aa2)
bb1+=bb2;
else if(aa2>aa1){
aa1=aa2;
bb1=bb2;
}
*aa=aa1;
*bb=bb1;
insert(x,aa1,bb1);
return;
}
Leave a comment below
