Katkat
Back

Sum the XOR of Every Cross-Array Pair

IBMSoftware Engineer · Online Assessment
EasySoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Tests bitwise frequency analysis and arithmetic optimization by reducing an O(N * M) cross-product XOR sum to an O(B * (N + M)) bit-by-bit contribution calculation.

Sum the XOR of Every Cross-Array Pair

You are given two integer arrays, nums1 and nums2.

Your task is to compute the total sum of nums1[i] ^ nums2[j] across all possible pairs (i, j) where 0 <= i < len(nums1) and 0 <= j < len(nums2).

Since the array lengths can be large, an O(len(nums1) * len(nums2)) brute-force solution will exceed the time limit.

Function Signature

def total_cross_xor_sum(nums1: list[int], nums2: list[int]) -> int:
    pass

Constraints

  • 1 <= len(nums1), len(nums2) <= 10^5
  • 0 <= nums1[i], nums2[j] <= 10^9

Examples

Example 1:

Input: nums1 = [1, 2], nums2 = [3, 4]
Output: 14
Explanation:
The pairs are:
- nums1[0] ^ nums2[0] = 1 ^ 3 = 2
- nums1[0] ^ nums2[1] = 1 ^ 4 = 5
- nums1[1] ^ nums2[0] = 2 ^ 3 = 1
- nums1[1] ^ nums2[1] = 2 ^ 4 = 6
Total sum = 2 + 5 + 1 + 6 = 14.

Example 2:

Input: nums1 = [0, 5], nums2 = [5]
Output: 5
Explanation:
- 0 ^ 5 = 5
- 5 ^ 5 = 0
Total sum = 5 + 0 = 5.

Edge Cases to Consider

  • Elements with value 0.
  • Arrays containing duplicate values.
  • Values up to 10^9 (which fit within a 30-bit representation: 2^29 <= 10^9 < 2^30).
  • Result exceeding standard 32-bit signed integer limits (can reach up to 10^5 * 10^5 * 10^9 = 10^19, requiring 64-bit integer handling).

Hints

Hint 1

Rather than summing full numbers pair by pair, consider how much each bit position contributes to the final sum independently.

Hint 2

For bit position k, an XOR result has the k-th bit set if and only if one operand has bit k set and the other has bit k unset.

Hint 3

Count the number of set bits at position k in nums1 and nums2, then calculate how many pairs produce a 1 at bit k.

Follow-up questions

  • How would you modify the solution to compute the cross-array sum of bitwise AND (&) or bitwise OR (|)?
  • How would you handle a streaming variant where elements are continuously added to or removed from nums1 or nums2?
  • If the numbers could be negative and represented using standard 32-bit two's complement, what changes would be necessary?