HackerRank Demanding Money Problem Solution

In this post, we will solve HackerRank Demanding Money Problem Solution.

Killgrave wants to use his mind control powers to get money from the Justice League superheroes living in N houses in Happy Harbor that are numbered sequentially from 1 to N. There are M roads, and each road j connects two different houses, A; and Bj. Each superhero house i (where 1 ≤ i ≤N) has C; dollars stashed away for a rainy day.
As long as a superhero is home at house i, Killgrave knows they will hand over all of their saved money, C₁. Once he gets money from them, he moves on to the next house.
However, the superheroes are cunning; when Killgrave comes to house X, every neighbor immediately connected to house X by a single road skips town for a couple of days (making it impossible for Killgrave to get money from them). In other words, after Killgrave visits all the superheroes he wants, there will be no road in which he was able to get money from both houses on either end of the road.
What is the maximum amount of money Killgrave can collect from the superheroes, and how many different ways can killgrave get that amount of money? Two ways are considered to be different if the sets of visited houses are different.
Note: Killgrave can start at an arbitrary house and doesn’t have to only use the roads.

Input Format
The first line contains two space-separated integers, N (the number of houses) and M (the
number of roads), respectively.
The second line contains N space-separated integers, where each integer i describes the amount of money, C₁, at house i.
Each line j of the M subsequent lines contains two space-separated integers defining a road connecting houses Aj, and Bj. Every road connects a different pair of houses.

utput Format

Print two space-separated integers:

The first integer must denote the maximum amount of money Killgrave can get out of the Justice League.
The second integer must denote the number of different ways he can collect that amount of money.

Sample Input

Sample Output

8 2

Explanation

Killgrave has two possible courses of action:

Visit house 2 and get 8 dollars.
Visit houses 1 and 3 and get 2 + 6 = 8 dollars.
Both of these options result in 8 dollars, so we know that this is maximal. Thus, we print the maximum amount of money (8) followed by the number of ways he can get that amount of money (2) as two space-separated values on a single line.

HackerRank Demanding Money Problem Solution

Demanding Money C 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;
}

Demanding Money C++ Solution

#include <stdio.h>
#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

typedef pair<long,long> pii;
typedef long long ll;
typedef unsigned long long ull;

ll N, M;

long long ANSWER_MONEY = -1;
long long ANSWER_COMBINATIONS = 0;
ull zeroFactor;

vector<unsigned long long> masks(35);
vector<ll> monies(35); 

void solve(ll remaining, ll money, ll n, bool doCount) {
  //cout << remaining  << " "  << money  << " n:" << n << endl;

  if (n == N + 1) {
    if (money > ANSWER_MONEY) {
      ANSWER_MONEY = money;
      ANSWER_COMBINATIONS = 1;
    } else if (doCount && money == ANSWER_MONEY) {
      ANSWER_COMBINATIONS += 1;
    }
    return;
  }


  if ((remaining & (1ll << (n  - 1ll))) == 0) {
    solve(remaining, money, n + 1, doCount);
    return;
  }

  solve(remaining, money, n + 1, true);
  ll newMask = remaining & (~(masks[n]));
  solve(newMask, money + monies[n], n + 1, true);
}

int main () {

  cin >> N >> M; 

  for (ll i = 1; i <= N; i++) {
    scanf("%lld", &monies[i]);
  }

  vector<vector<ll> > G(N + 1);

  for (ll i = 0; i < M; i++) {
    ll a,b;
    scanf("%lld %lld", &a, &b);
    G[a].push_back(b);
    G[b].push_back(a);
  }

  ll START = (1ll << N) - 1ll;
  ll BASE_STATE = 0;
  ll zeroCount = 0;
  ll STARTING_MONEY = 0;

  for (ll i = 1; i <= N; i++) {
    ll m = 0;
    for (auto &j : G[i]) {
      m = m | (1ll << (j-1));
    }

    ll POS = 1ll << (i - 1);

    // always choose if no roads
    if (m == 0) {
      START = START ^ POS;
      BASE_STATE = BASE_STATE | POS;
      STARTING_MONEY += monies[i];

      if (monies[i] == 0) {
        zeroCount++;
      }
    }

    m = m | POS;
    masks[i]  = m;
  }

  zeroFactor = 1ll << zeroCount;
  solve(START, 0, 1, false);
  cout << ANSWER_MONEY + STARTING_MONEY  << " " << ANSWER_COMBINATIONS * zeroFactor << endl;

  return 0;
}

Demanding Money C Sharp Solution


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;


    class Solution
    {
        public static List<int>[] adj;
        public static int[] c;
        static long count = 0;
        public static int max = -1;
        static void Main(string[] args)
        
        {

            string s1 = Console.ReadLine();
            string[] s = s1.Split(' ');
            int n = Convert.ToInt32(s[0]);
            int m = Convert.ToInt32(s[1]);
            adj = new List<int>[n+1];
            for (int i = 0; i <=n; i++)
            {
                adj[i] = new List<int>();
            }
            int a, b;
            c = new int[n + 1];
            string houses1 = Console.ReadLine();
            string[] houses = houses1.Split(' ');
            for (int i = 1; i <=n; i++)
            {
                c[i] = Convert.ToInt32( houses[i - 1]);
            }

            for (int i = 1; i <=m; i++)
            {
                string roads = Console.ReadLine();
                string[] road = roads.Split(' ');
                 a = Convert.ToInt32(road[0]);
                 b = Convert.ToInt32(road[1]);
                 adj[a].Add(b);
                 adj[b].Add(a);
                
            }

            bool[] visited = new bool[n + 1];
            List<int>[] scc = new List<int>[35];

            for (int i = 0; i < 35; i++)
            {
                scc[i] = new List<int>();
            }

            int index = 0;
            List<int> q = new List<int>();
            int u;
            for (int i = 1; i <=n; i++)
            {
                if(!visited[i])
                {
                    index++;
                    {
                        q.Add(i);
                        visited[i] = true;
                        scc[index].Add(i);
                        while(q.Count() != 0)
                        {
                            int z = q.Count();
                            int x = z;
                            u = q.ElementAt(z-1);
                             q.RemoveAt(z-1);
                            foreach(int v in adj[u])
                            {
                                if(!visited[v])
                                {
                                    visited[v] = true;
                                    q.Add(v);
                                    scc[index].Add(v);
                                }
                            }


                        }
                    }
                }
                
            }

            int maxRes = 0;
            long countRes = 1;
            for (int i = 1; i <=index; i++)
            {
                count = 0;
                max = -1;
                check(new List<int>(), scc[i]);
                maxRes = maxRes + max;
                countRes = countRes * count;
                
            }

            Console.WriteLine(maxRes + " " + countRes);


            
        }
        static void check(List<int> old,List<int> rem)
        {
            int val, a;
            if(rem.Count() ==0)
            {
                val = 0;
                foreach (var item in old)
                {
                    val = val + c[item];
                }
                if(val == max)
                {
                    count++;
                }
                if(val > max)
                {
                    count = 1;
                    max = val;
                }
                return;
            }

            List<int> l1, l2,l3;
            l1 = new List<int>();
            l2 = new List<int>();
            l3 = new List<int>();
            foreach (var item in rem)
            {
                l2.Add(item);
            }
            int z = l2.Count();
            a = l2.ElementAt((z-1));
            l2.RemoveAt(z-1);
            foreach (var item in old)
            {
                l1.Add(item);
            }
            check(old, l2);
            l1.Add(a);
            if(l2.Count()!= 0)
            {
                foreach (var item in l2)
                {
                    if(!adj[a].Contains(item))
                    {
                        l3.Add(item);
                    }
                }
            }
            check(l1, l3);
            return;
        }
    }

Demanding Money Java Solution

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

public class Solution {

    /*
     * Complete the demandingMoney function below.
     */
    private static long maxMoney = Integer.MIN_VALUE;
    private static Map<Long, Long> solutions;
    private static Set<Integer>[] graph;
    private static int[] moneys;
    
    static long[] demandingMoney(int[] inputMoneys, int[][] roads) 
    {
        if (inputMoneys == null || inputMoneys.length == 0)
        {
            return new long[] {0, 0};
        }
        
        int n = inputMoneys.length;
        moneys = inputMoneys;
        graph = new Set[n+1];
        solutions = new HashMap<>();
    
        for (int i = 1; i <= n; i++)
        {
            graph[i] = new HashSet<>();
        }
        
        for (int[] road : roads)
        {
            int max = road[0] > road[1] ? road[0] : road[1];
            int min = road[0] > road[1] ? road[1] : road[0];
            graph[min].add(max);
            
            graph[min].add(min);
            graph[max].add(max);
        }
        
        Set<Integer> visited = new HashSet<>();
        int soloMoney = 0;
        int zeroCount = 0;
        
        for (int i = 1; i <= n; i++)
        {
            if (graph[i].size() == 0)
            {
                visited.add(i);
                soloMoney += moneys[i-1];
                zeroCount += moneys[i-1] == 0 ? 1 : 0;
            }
        }
        
        solutions.put(0L, 1L);
        for (int start = 1; start <= n; start++)
        {
            if (!visited.contains(start))
            {
                search(start, visited, 0L);
            }
        }
        
        long result = soloMoney;
        long count = 1;
        
        for (int i = 0; i < zeroCount; i++)
        {
            count *= 2L;
        }
        
        if (maxMoney != Integer.MIN_VALUE)
        {
            count *= solutions.get(maxMoney);
            result += maxMoney;
        }
        
        return new long[] { result, count };
    }
    
    private static void search(int start, Set<Integer> visited, long totalMoney)
    {
        totalMoney += moneys[start-1];
        solutions.put(totalMoney, solutions.getOrDefault(totalMoney, 0L) + 1L);
        maxMoney = Math.max(maxMoney, totalMoney);
        
        Set<Integer> removed = new HashSet<>();
        for (int neighbor : graph[start])
        {
            if (!visited.contains(neighbor))
            {
                visited.add(neighbor);
                removed.add(neighbor);
            }
        }
        
        for (int next = start+1; next <= moneys.length; next++)
        {
            if (visited.contains(next))
            {
                continue;
            }
            
            search(next, visited, totalMoney);
        }
        
        visited.removeAll(removed);
    }

    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])*");

        int n = Integer.parseInt(nm[0]);

        int m = Integer.parseInt(nm[1]);

        int[] money = new int[n];

        String[] moneyItems = scanner.nextLine().split(" ");
        scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

        for (int moneyItr = 0; moneyItr < n; moneyItr++) {
            int moneyItem = Integer.parseInt(moneyItems[moneyItr]);
            money[moneyItr] = moneyItem;
        }

        int[][] roads = new int[m][2];

        for (int roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
            String[] roadsRowItems = scanner.nextLine().split(" ");
            scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");

            for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
                int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr]);
                roads[roadsRowItr][roadsColumnItr] = roadsItem;
            }
        }

        long[] result = demandingMoney(money, roads);

        for (int resultItr = 0; resultItr < result.length; resultItr++) {
            bufferedWriter.write(String.valueOf(result[resultItr]));

            if (resultItr != result.length - 1) {
                bufferedWriter.write(" ");
            }
        }

        bufferedWriter.newLine();

        bufferedWriter.close();

        scanner.close();
    }
}

Demanding Money JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the demandingMoney function below.
 */
function demandingMoney(money, roads) {
    /*
     * Write your code here.
     */
    let adj = [];
    for (let road of roads) {
        if (!adj[road[0]]) adj[road[0]] = [road[1]];
        else adj[road[0]].push(road[1]);
        if (!adj[road[1]]) adj[road[1]] = [road[0]];
        else adj[road[1]].push(road[0]);
    }
    function visit(unvisited, visited = [], bag = 0) {
        let res = [bag];
        for (let node of unvisited) {
            // console.log("checking", node, visited);
            let vis = Array.from(visited), unv = [], maxn = Math.max(-1, ...visited);
            if (node <= maxn) continue;
            vis.push(node);
            for (let n of unvisited) {
                if (!(adj[node] && adj[node].indexOf(n) > -1)
                    && n != node) unv.push(n);
            }
            // console.log("visiting", node, unv, unvisited);
            let visitAll = visit(unv, vis, bag + money[node - 1]);
            let max = Math.max(bag, ...visitAll, ...res);
            res = res.concat(visitAll).filter(x => x == max);
            // console.log("exiting", node, res);
        }
        return res;
    }
    let houses = money.map((x, i) => i + 1);
    let neighborhood = Array.from(houses);
    for (let i = neighborhood.length - 1; i >= 0; i--){
        if (!adj[i + 1]) continue;
        let minAdj = Math.min(i + 1, ...adj[i + 1]);
        let curAdj = adj[i + 1].map(x => neighborhood[x - 1]);
        neighborhood = neighborhood.map(x=>curAdj.indexOf(x)>-1?minAdj:x);
    }
    let nbId = Array.from(new Set(neighborhood));
    neighborhood = nbId.map(x => neighborhood.
        map((y, i) => x == y ? i + 1 : -1).filter(y => y > -1));
    console.log(neighborhood);
    neighborhood = neighborhood.map(x => visit(x));
    console.log(neighborhood);
    let max = neighborhood.reduce((p, c) => p + c[0], 0);
    let n = neighborhood.reduce((p, c) => p * c.length, 1);
    return [max,n]
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const nm = readLine().split(' ');

    const n = parseInt(nm[0], 10);

    const m = parseInt(nm[1], 10);

    const money = readLine().split(' ').map(moneyTemp => parseInt(moneyTemp, 10));

    let roads = Array(m);

    for (let roadsRowItr = 0; roadsRowItr < m; roadsRowItr++) {
        roads[roadsRowItr] = readLine().split(' ').map(roadsTemp => parseInt(roadsTemp, 10));
    }

    let result = demandingMoney(money, roads);

    ws.write(result.join(" ") + "\n");

    ws.end();
}

Demanding Money Python Solution

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'demandingMoney' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts following parameters:
#  1. INTEGER_ARRAY money
#  2. 2D_INTEGER_ARRAY roads
#

def demandingMoney(money, roads):
    #
    # Write your code here.
    #
    x = {}
    roadSet = {i: set() for i in range(len(money))}
    for roadpair in roads:
        a = roadpair[0] - 1
        b = roadpair[1] - 1
        roadSet[a].add(b)
        roadSet[b].add(a)

    houseSet = set([i for i in range(len(money))])

    def max_money(houseSet):
        if not houseSet:
            return (0, 1)
        fsh = frozenset(houseSet)
        if fsh in x:
            return x[fsh]
        nh = houseSet.pop()
        money_a, waiting_a = max_money(houseSet - roadSet[nh])
        money_a += money[nh]
        money_b, waiting_b = max_money(houseSet)

        if money_a > money_b:
            x[fsh] = (money_a, waiting_a)
        elif money_b > money_a:
            x[fsh] = (money_b, waiting_b)
        else:
            x[fsh] = (money_a, waiting_a + waiting_b)
        return x[fsh]

    return max_money(houseSet)
                  
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nm = input().split()

    n = int(nm[0])

    m = int(nm[1])

    money = list(map(int, input().rstrip().split()))

    roads = []

    for _ in range(m):
        roads.append(list(map(int, input().rstrip().split())))

    result = demandingMoney(money, roads)

    fptr.write(' '.join(map(str, result)))
    fptr.write('\n')

    fptr.close()

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python