CF 102697153 - Parity Checker
We receive exactly nine binary digits. The first digit is a parity bit, while the remaining eight digits form the transmitted byte.
Rating: -
Tags: -
Solve time: 6m 41s
Verified: yes
Solution
Problem Understanding
We receive exactly nine binary digits. The first digit is a parity bit, while the remaining eight digits form the transmitted byte. The parity convention used by the problem is slightly unusual: the parity bit is 1 when the byte contains an even number of 1 bits, and 0 when the byte contains an odd number of 1 bits. We must determine whether the received nine-bit sequence follows that rule.
The easiest way to express the rule is to look at all nine bits together. If the byte contains an even number of 1s, the first bit must be 1, so the total number of 1s in the nine-bit sequence is odd. If the byte contains an odd number of 1s, the first bit must be 0, and the total is again odd. Thus, a valid transmission always contains an odd number of 1s among all nine positions.
The input size is fixed, so there is no meaningful large-n performance issue. We inspect at most nine characters, which is constant work regardless of the input. The one-second time limit and 256 MB memory limit are far more generous than necessary for such a small input. An approach involving even a small amount of exponential enumeration would still be unnecessary, while a single pass is immediately sufficient.
There are a few cases where blindly checking only the eight data bits can lead to mistakes. For example, 100000000 has zero 1s in the byte, which is even, so the parity bit should be 1. The correct output is NO ERROR. A careless implementation that expects the entire sequence to contain an even number of 1s would incorrectly reject it.
The opposite situation is 000000001. The byte contains one 1, which is odd, so the parity bit should be 0. The correct output is NO ERROR. Checking only whether the byte itself has even parity would miss the fact that the first bit is supposed to encode the opposite value for odd parity.
The all-zero sequence 000000000 is also useful. Its byte contains zero 1s, so the required parity bit is 1, not 0. The correct output is TRANSMISSION ERROR. This catches implementations that accidentally assume an all-zero message is always valid.
Approaches
A direct approach is to count the number of 1s in the eight-bit message, determine whether that count is even or odd, and compare the required parity bit with the first input character. This is correct because the parity definition is exactly a condition on those eight data bits. The worst case examines all eight data positions, so it performs eight bit inspections and one comparison. Since the input always has exactly nine characters, this is constant time and is easily fast enough.
The more useful observation is that we do not actually need to separate the parity bit from the message. Suppose the byte contains k ones. If k is even, the first bit must be 1, giving k + 1, an odd number of total ones. If k is odd, the first bit must be 0, leaving k, which is also odd. A valid sequence is consequently characterized by one simple condition: its nine bits contain an odd number of 1s.
That reduces the problem to counting the 1s in the entire string and checking the parity of that count. The brute-force version works because there are only eight data bits, but it reasons about two separate pieces of the input. The parity observation removes that distinction and turns the validation into a single condition.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force | O(9) = O(1) | O(1) | Accepted |
| Optimal | O(9) = O(1) | O(1) | Accepted |
Algorithm Walkthrough
- Read the nine-bit string. The input contains no spaces inside the sequence, so it can be read directly as one string.
- Count how many characters in the complete nine-bit string are equal to
'1'. We count all nine positions because the parity rule can be expressed entirely in terms of the total number of ones. - Check whether the count is odd. A valid transmission must have an odd total number of ones, as derived from the definition of the parity bit.
- Print
NO ERRORwhen the count is odd. Otherwise, printTRANSMISSION ERROR.
Why it works: let the number of 1s in the eight-bit message be k. When k is even, validity requires the parity bit to be 1, so the complete sequence contains k + 1 ones, which is odd. When k is odd, validity requires the parity bit to be 0, so the complete sequence contains k ones, which is also odd. Thus every valid sequence has an odd number of ones. Conversely, if the complete sequence has an odd number of ones, an even data count forces the first bit to be 1, while an odd data count forces it to be 0, exactly matching the required parity bit. The condition is both necessary and sufficient.
Python Solution
import sys
input = sys.stdin.readline
def solve(s):
ones = s.count('1')
if ones % 2 == 1:
return "NO ERROR"
return "TRANSMISSION ERROR"
def main():
s = input().strip()
print(solve(s))
if __name__ == "__main__":
main()
The solve function receives the nine-bit sequence and uses count('1') to obtain the total number of ones. There is no need to convert the sequence into an integer because the problem is concerned with individual binary digits, not their numeric value.
The modulo operation checks whether the total count is odd. The output strings are reproduced exactly, including their spaces and capitalization.
There are no indexing operations, so there is no off-by-one risk from accidentally treating the parity bit as part of the byte or omitting the final data bit. Python integers also have no overflow concern, although the largest count here is only nine.
The call to strip() removes the newline produced by standard input. Since the input contains exactly nine binary digits, it does not remove any meaningful character from the sequence.
Worked Examples
Sample 1
The provided sample is 100110101.
| Step | Sequence | Number of 1s |
Parity |
|---|---|---|---|
| 1 | 100110101 |
5 | Odd |
| 2 | 100110101 |
5 | Valid |
| 3 | 100110101 |
5 | NO ERROR |
There are five ones in the complete sequence. Since five is odd, the parity condition is satisfied and the transmission is valid.
Example 2
Consider 100000000.
| Step | Sequence | Number of 1s |
Parity |
|---|---|---|---|
| 1 | 100000000 |
1 | Odd |
| 2 | 100000000 |
1 | Valid |
| 3 | 100000000 |
1 | NO ERROR |
The eight-bit message is 00000000, which contains zero ones and therefore has even parity. The leading parity bit is correctly 1. The complete sequence consequently has one 1, which is odd.
Example 3
Consider 000000000.
| Step | Sequence | Number of 1s |
Parity |
|---|---|---|---|
| 1 | 000000000 |
0 | Even |
| 2 | 000000000 |
0 | Invalid |
| 3 | 000000000 |
0 | TRANSMISSION ERROR |
The message contains zero ones, so its parity is even and the leading bit should have been 1. The zero leading bit makes the transmission invalid.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(1) | Exactly nine characters are inspected. |
| Space | O(1) | Only the input string and a single integer count are stored. |
The input size is fixed at nine bits, so the solution performs only a constant amount of work. It is comfortably within the one-second time limit and uses negligible memory compared with the 256 MB limit.
Test Cases
# helper: run solution on input string, return output string
import sys
import io
def solve(s):
ones = s.count('1')
if ones % 2 == 1:
return "NO ERROR"
return "TRANSMISSION ERROR"
def run(inp: str) -> str:
old_stdin = sys.stdin
sys.stdin = io.StringIO(inp)
try:
s = sys.stdin.readline().strip()
return solve(s) + "\n"
finally:
sys.stdin = old_stdin
# provided sample
assert run("100110101\n") == "NO ERROR\n", "sample 1"
# all zeros: even data parity requires a leading 1
assert run("000000000\n") == "TRANSMISSION ERROR\n", "all zeros"
# all ones: eight data ones are even, so the leading 1 is correct
assert run("111111111\n") == "NO ERROR\n", "all ones"
# one data bit set: odd data parity requires a leading 0
assert run("000000001\n") == "NO ERROR\n", "single data one"
# correct data parity but wrong parity bit
assert run("100000001\n") == "TRANSMISSION ERROR\n", "wrong leading parity bit"
| Test input | Expected output | What it validates |
|---|---|---|
000000000 |
TRANSMISSION ERROR |
All-zero boundary case and required leading parity bit |
111111111 |
NO ERROR |
All-equal values and maximum possible number of ones |
000000001 |
NO ERROR |
Odd data parity with the smallest nonzero byte |
100000001 |
TRANSMISSION ERROR |
Correctly detecting an incorrect leading parity bit |
Edge Cases
For 100000000, the algorithm counts exactly one 1. The count is odd, so it prints NO ERROR. The underlying byte has zero ones, an even count, and the leading 1 is exactly the required parity bit.
For 000000001, the algorithm again counts one 1, so it prints NO ERROR. Here the byte has one 1, which is odd, and the leading parity bit is correctly 0. This demonstrates why the parity bit cannot simply be expected to equal the parity of the byte.
For 000000000, the algorithm counts zero ones. Zero is even, so it prints TRANSMISSION ERROR. The byte has even parity, but the first bit is 0 when it should be 1.
For 111111111, the algorithm counts nine ones. Nine is odd, so it prints NO ERROR. The eight-bit message contains eight ones, which is even, making the leading 1 correct. This is also a useful check that the final data position is included in the count.