Validating Binary Tree Nodes

Given n nodes labeled from 0 to n-1, each with optional left (leftChild) and right (rightChild) children (denoted by -1 if absent), check if all nodes form exactly one valid binary tree.

Solution Code

const isValidBinaryTree = function(nodeCount, leftChildren, rightChildren) {
    // Track parent of each node (-1 initially means no parent)
    const parentMap = new Array(nodeCount).fill(-1);
    for (let i = 0; i < nodeCount; i++) {
        // Validate left child
        if (leftChildren[i] !== -1) {
            if (parentMap[leftChildren[i]] !== -1) return false;
            parentMap[leftChildren[i]] = i;
        }
        // Validate right child
        if (rightChildren[i] !== -1) {
            if (parentMap[rightChildren[i]] !== -1) return false;
            parentMap[rightChildren[i]] = i;
        }
    }

    let rootCount = 0;
    let rootIndex = -1;
    for (let i = 0; i < nodeCount; i++) {
        if (parentMap[i] === -1) {
            rootCount++;
            if (rootCount > 1) return false;
            rootIndex = i;
        }
    }

    // Verify all nodes are reachable from the single root
    let visitedCount = 0;
    const traverse = (index) => {
        visitedCount++;
        if (leftChildren[index] !== -1) traverse(leftChildren[index]);
        if (rightChildren[index] !== -1) traverse(rightChildren[index]);
    };
    traverse(rootIndex);
    return visitedCount === nodeCount;
};

Forming the Largest Mlutiple of Three

Given an array of digits, connect them in any order to form the largest possible multiple of 3 as a string. If impossible, return an empty string.

Key Observasions

• A number is divisible by 3 if the sum of its digits is divisible by 3.
• Remove minimal digits to adjust the sum modulo 3 to 0, preserving as many high digits as posssible.

Solution Code

const largestMultipleOfThree = function(digits) {
    // Count occurrences of each digit (0-9)
    const digitCount = new Array(10).fill(0);
    let totalSum = 0;
    digits.forEach(d => {
        digitCount[d]++;
        totalSum += d;
    });

    // Helper function to remove digits with specific remainder
    const removeDigit = (remainder) => {
        for (let i = remainder; i <= 9; i += 3) {
            if (digitCount[i] > 0) {
                digitCount[i]--;
                totalSum -= i;
                return true;
            }
        }
        return false;
    };

    // Adjust sum to be divisible by 3
    if (totalSum % 3 === 1) {
        if (!removeDigit(1)) {
            removeDigit(2);
            removeDigit(2);
        }
    } else if (totalSum % 3 === 2) {
        if (!removeDigit(2)) {
            removeDigit(1);
            removeDigit(1);
        }
    }

    // Handle all-zero case
    if (totalSum === 0 && digitCount[0] > 0) return "0";

    // Build the largest number from remaining digits
    let result = "";
    for (let i = 9; i >= 0; i--) {
        while (digitCount[i]-- > 0) {
            result += i;
        }
    }

    return result;
};