Ccodeforces Contest 1991: B. AND Reconstruction

Simple O(n) soultion explained

Problem

https://codeforces.com/contest/1991/problem/B

Intuition

For i <= 1 <= n -1, we have

• b[i] = a[i] & a[i + 1]
• b[i + 1] = a[i + 1] & a[i + 2]

For the first and last element in a, we can simply have

• a[0] = b[0]
• a[n] = b[n — 1]

since all the 0 and 1 bits sould remain after taking bitwise & on a[0] and a[1], same for a[n — 1] & a[n] .

We can reconstruct a[i + 1] by b[i] and b[i + 1], since

• After taking the bitwise & on a[i] and a[i+ 1], all the 0 bits from a[i + 1] will remain in b[i].
• All the 0 bits from a[i + 1] will remain in b[i + 1], after performing a[i + 1] & a[i + 2]
• So, if we take b[i] | b[i + 1], we can reconstruct all 0 bits from a[i + 1], and some 1 bits.
• We can then validate a[i + 1], by checking if a[i + 1] & a[i] = b[i] and a[i + 1] & a[i+ 2] = b[i + 1]. If not, it means we couldn’t reconstruct a[i + 1] from b[i] and b[i + 1], which means we have to fail fast and return -1.

Complexity Analysis

• Time Complexity: O(n)
• Spcae Complexity: O(1)

Code

from typing import List

def main():
    t = input()
    for _ in range(int(t)):
        n = input()
        a = [0 for _ in range(int(n))]
        b = [int(b_i) for b_i in input().split(" ")]
        result = reconstruct(a, b)
        print(*result)


def reconstruct(a: List[int], b: List[int]) -> List[int]:
    for i in range(len(a)):
        if i == 0:
            a[i] = b[i]
        elif i == len(a) - 1:
            a[i] = b[-1]
        else:
            a[i] = b[i] | b[i - 1]
        
        if i > 0 and b[i -1] != a[i] & a[i-1]:
            return [-1]

    return a


main()