Telemetry Alarm Tallies
For each array value, count earlier values with XOR in a given range
A spacecraft sends a sequence of unsigned telemetry readings. Mission control compares each new reading with every earlier reading to detect changes in selected bit positions.
The contrast score of two readings is their bitwise XOR. A comparison triggers an alarm when its contrast score is in the inclusive interval [low, high].
Given readings, low, and high, return an integer array tallies of the same length as readings, where tallies[i] is the number of indices j satisfying both:
0 <= j < ilow <= (readings[i] XOR readings[j]) <= high
Each earlier transmission counts separately, even if several transmissions contain the same reading. A reading is never compared with itself.
Examples
Example 1
Input: readings = [1,2,7,1], low = 2, high = 5 Output: [0,1,1,1]
The second reading has contrast score 3 with the first. The third has scores 6 and 5 with the earlier readings. The fourth repeats the first reading, giving scores 0, 3, and 6; only scores in the requested band trigger alarms.
Example 2
Input: readings = [9,9,4,9], low = 0, high = 0 Output: [0,1,0,2]
The band contains only zero, so a transmission triggers an alarm exactly when an earlier transmission has the same reading. Repeated transmissions are counted individually.
Example 3
Input: readings = [0,65535,12], low = 0, high = 65535 Output: [0,1,2]
Every possible 16-bit contrast score lies in this band, so each transmission triggers one alarm for every earlier transmission.
Constraints
- 0 <= readings.length <= 7000
- 0 <= readings[i] <= 65535
- 0 <= low <= high <= 65535
The reference solution uses a counted binary trie over 16 bits. It takes O(16n) time and O(16n) space, where n is the number of readings. The upper rank-query threshold may be 65536 even though readings themselves are at most 65535.
Hints
Show hint 1Hint 1
Process transmissions in order, keeping only earlier readings in a binary trie. Store how many readings pass through each node.
Show hint 2Hint 2
To count XOR scores in an inclusive band, subtract the number of scores less than low from the number less than high + 1. Examine the threshold bits from most significant to least significant.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you adapt the method if each transmission had its own low and high thresholds?
- How could the trie support retracting a previously received transmission while continuing to process the stream?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem