beautifulQuadruples.js

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

function beautifulQuadruples(a, b, c, d) {
    // sorting values for consistency and order doesn't matter with XOR operation
    const sortedInput = [a, b, c, d]
    sortedInput.sort((val1, val2) => val1 - val2)
    const [A, B, C, D] = sortedInput

    // Given the maximum number D, the most significant bit sets the limit for
    // how much space is needed for C_D_memo
    const maxXor = 2 ** D.toString(2).length

    // Store combo counts by C_D XOR combo
    const CDMemo = new Array(maxXor).fill(0)
    // 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
    let validCDTotalCombos = 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 (let Y = 1; Y <= C; Y++) { // O(C * D)
        for (let Z = Y; Z <= D; Z++) {
            // helps enforce only combos where Y <= Z
            const YZXORCombo = Y ^ Z
            CDMemo[YZXORCombo] += 1
            validCDTotalCombos += 1 // keep count in sync with memo list
        }
    }
    
    // handle A^B combos AND combining with all previously made C^D combos
    let totalValidCombos = 0

    // Processing W inside of the X loop helps ensure only combos have X <= Y
    // (see 2nd inner "clean up" loop)
    for (let X = 1; X <= B; X++) { // O(B * (A + D))
        for (let W = 1; W <= Math.min(X, A); W++) {
            // This odd arrangement ensures W <= X
            const WXXORCombo = W ^ X

            const WXXORZeros = CDMemo[WXXORCombo]
            // remove invalid combos where W^X==Y^Z, which would result in W^X^Y^Z==0
            const additional_valid_combos = validCDTotalCombos - WXXORZeros
            totalValidCombos += 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 (let Z = X; Z <= D; Z++) {
            const dedupeCombo = X ^ Z
            CDMemo[dedupeCombo] -= 1
            validCDTotalCombos -= 1 // keep count in sync with memo list
        }
    }
    // Time Complexity: O(C * D) + O(B * (A + D))
    return totalValidCombos
}