beautiful_quadruples.py

# source: https://www.hackerrank.com/challenges/xor-quadruples/problem
# video: https://youtu.be/LyOpIRgobsc

def beautifulQuadruples(a, b, c, d):
    # sorting values for consistency and order doesn't matter with XOR operation
    sorted_input = sorted([a, b, c, d])
    A, B, C, D = sorted_input

    # Given the maximum number D, the most significant bit sets the limit for
    # how much space is needed for C_D_memo
    max_xor = 2 ** (len(bin(D)) - 2)
    
    # Store combo counts by C_D XOR combo
    C_D_memo = [0] * max_xor
    # Efficiently keep track of total C_D XOR combo count stored in memo
    # Will need to keep this count in sync with C_D_memo
    valid_c_d_total_combos = 0

    # NOTE: In order to avoid duplicates, we'll only consider combos
    # that adhere to a sorted order W <= X <= Y <= Z
    # For example: 1 1 1 2 and 1 1 2 1 and 1 2 1 1 are all the same combo
    # But we'll arbitrarily count 1 1 1 2 only
    
    # store all C^D combos
    for Y in range(1, C + 1):  # O(C * D)
        for Z in range(Y, D + 1):  # helps enforce only combos where Y <= Z
            Y_Z_XOR_combo = Y ^ Z
            C_D_memo[Y_Z_XOR_combo] += 1
            valid_c_d_total_combos += 1  # keep count in sync with memo list

    # handle A^B combos AND combining with all previously made C^D combos
    total_valid_combos = 0
    
    # Processing W inside of the X loop helps ensure only combos have X <= Y
    # (see 2nd inner "clean up" loop)
    for X in range(1, B + 1):  # O(B * (A + D))
        for W in range(1, min(X, A) + 1):  # This odd arrangement ensures W <= X
            W_X_XOR_combo = W ^ X
            W_X_XOR_zeros = C_D_memo[W_X_XOR_combo]
            # remove invalid combos where W^X==Y^Z, which would result in W^X^Y^Z==0
            additional_valid_combos = valid_c_d_total_combos - W_X_XOR_zeros
            total_valid_combos += additional_valid_combos

        # This "Clean up" loop removes combos from future consideration, since they'll
        # only become duplicates later
        # The memo list contains all C_D combos we'll combine with the W_X combos
        # However, since we're looping through all values of X,
        # the Y_Z combos where X > Y will break the W <= X <= Y <= Z sorted combo rule
        # By elminating these Y_Z (really X_Y) combos now, we won't consider them during
        # the next loop.
        # For example: 
        # A,B,C,D = 1,2,2,3
        # We're currently at X = 1
        # In the next loop, X will be 2
        # In that next loop we do NOT want to consider 1,2,1,1 OR 1,2,1,2 OR 1,2,1,3
        # Before we even get to X = 2, we'll remove all 1^Z (X^Z) combos (1^1, 1^2, 1^3) now
        for Z in range(X, D + 1):
            dedupe_combo = X ^ Z
            C_D_memo[dedupe_combo] -= 1
            valid_c_d_total_combos -= 1  # keep count in sync with memo list
    
    # Time Complexity: O(C * D) + O(B * (A + D))
    return total_valid_combos