We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Achievable Transfer Requests

Number: 1723

Difficulty: Hard

Paid? No

Companies: Google, Amazon

Problem Description

Given n buildings and an array of requests where each request represents a transfer from one building to another, determine the maximum number of requests that can be achieved such that for every building the net change (inflow minus outflow) is zero.

Key Insights

  • The solution requires checking subsets of transfer requests.
  • Brute-force subset enumeration is feasible given the maximum of 16 requests.
  • For each subset, compute a net change array for all buildings.
  • The subset is valid if the net change for every building is zero.
  • Bit Manipulation is used to represent and iterate over subsets effectively.

Space and Time Complexity

Time Complexity: O(2^m * (n + m)), where m is the number of requests. Space Complexity: O(n) for the net change array.

Solution

We approach the problem by using bitmask enumeration to try every possible combination of requests. For each combination, we update an array representing the net change of employees in each building. A valid combination has all entries equal to zero. We maximize the count of requests in valid subsets. The key trick is to iterate over all 2^m combinations (where m is the number of requests) and use a bitmask to include/exclude each request. This approach works because m is small (up to 16), making the brute-force search efficient.

Code Solutions

# Python solution using bitmask enumeration
def maximumRequests(n, requests):
    m = len(requests)
    max_requests = 0
    # Iterate over each possible subset of requests represented by a bitmask
    for mask in range(1 << m): 
        net_change = [0] * n
        count = 0
        # Iterate through all requests using bit positions in the mask
        for i in range(m):
            if mask & (1 << i):
                f, t = requests[i]
                net_change[f] -= 1
                net_change[t] += 1
                count += 1
        # Check if the current combination is valid (net change of 0 for each building)
        if all(change == 0 for change in net_change):
            max_requests = max(max_requests, count)
    return max_requests

# Example usage:
#print(maximumRequests(5, [[0,1],[1,0],[0,1],[1,2],[2,0],[3,4]]))
← Back to All Questions