A remote relay tower receives a stream of calibration pulses, one at a time. Each pulse carries a single bit, 0 or 1. As pulses arrive, ground control keeps appending each new bit to the right of a growing binary number (so after the pulses 1, 0, 1 the accumulated code is the binary number 101, i.e. five, with the earliest pulse as the most significant bit). Every time a new pulse lands, ground control needs to know whether the accumulated code, read as a binary number so far, is currently a multiple of five — codes that are multiples of five trigger an automatic calibration event at the tower.
Given the pulses in the order they arrive, report, for every prefix of the stream (i.e., after each pulse is appended), whether the binary number formed by that prefix is divisible by five.
Line 1: a single integer n — the number of pulses. Line 2: n integers separated by spaces, each either 0 or 1 — the pulses in the order they arrive.
Print n integers separated by single spaces on one line: the i-th integer is 1 if the binary number formed by the first i pulses (the prefix ending at the i-th pulse, counting from 1) is divisible by 5, and 0 otherwise. (The value 0 itself counts as divisible by 5.)
1 <= n <= 30000 Each pulse is 0 or 1.
Example 1
Input
5 0 1 1 0 1
Expected
1 0 0 0 0
Explanation
Reading pulses left to right, the growing binary codes are 0, 01, 011, 0110, 01101, i.e. decimal 0, 1, 3, 6, 13. Only the first (0) is a multiple of five, so the output is 1 0 0 0 0.
Example 2
Input
5 1 0 1 0 0
Expected
0 0 1 1 1
Explanation
The growing binary codes are 1, 10, 101, 1010, 10100, i.e. decimal 1, 2, 5, 10, 20. The codes 5, 10 and 20 are multiples of five, so the output is 0 0 1 1 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →