# 2.07.2023 [1601. Maximum Number of Achievable Transfer Requests]

Max edges to make all counts `in == out` edges in graph

2.07.2023

1601. Maximum Number of Achievable Transfer Requests hard
blog post

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/263

Problem TLDR

Max edges to make all counts in == out edges in graph

Intuition

Let’s observe some examples:

All requests are valid if count of incoming edges are equal to outcoming.
One possible solution is to just check each combination of edges.

Approach

Let’s use bitmask to traverse all combinations, as total number 16 can fit in Int

Complexity

• Time complexity:
  O(n2^r)

• Space complexity:
  O(n2^r)

Code

fun maximumRequests(n: Int, requests: Array<IntArray>): Int =
    (0..((1 shl requests.size) - 1)).filter { mask ->
        val fromTo = IntArray(n)
        requests.indices.filter { ((1 shl it) and mask) != 0 }.forEach {
            val (from, to) = requests[it]
            fromTo[from] -= 1
            fromTo[to] += 1
        }
        fromTo.all { it == 0 }
    }.map { Integer.bitCount(it) }.max()!!