OrAndSum | Topcoder Archive

Problem Statement

You are given two long[]s: pairOr and pairSum. Each of these arrays will contain n non-negative integers.

Determine whether it is possible to construct a sequence x[0], ..., x[n] of nonnegative integers with the following properties:

for each i between 0 and n-1, inclusive, x[i] or x[i+1] = pairOr[i]
for each i between 0 and n-1, inclusive, x[i] + x[i+1] = pairSum[i]

Note that the sequence x should contain n+1 elements: one more than the length of each of the given arrays.

Return "Possible" if we can find at least one such sequence x, and "Impossible" if not.

Definition

Class:: OrAndSum
Method:: isPossible
Parameters:: long[], long[]
Returns:: String
Method signature:: String isPossible(long[] pairOr, long[] pairSum)
(be sure your method is public)

Constraints

pairOr will contain between 1 and 50 elements, inclusive.
pairOr and pairSum will contain the same number of elements.
Each element in pairOr will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.
Each element in pairSum will be between 0 and 1,000,000,000,000,000,000 (10^18), inclusive.

Examples

```
{7}
```
```
{11}
```
```
Returns: "Possible"
```
One of the solutions is {5,6}.
```
{11}
```
```
{7}
```
```
Returns: "Impossible"
```
The sum of two numbers will always be greater than or equal to their bitwise or.

{3,3,7,5,7}

{3,5,7,9,11}

Returns: "Possible"

One of the solutions is {1,2,3,4,5,6}.

{1,100,1000}

{100,1000,10000}

Returns: "Impossible"

{261208776456074191,261208776456074191,261208776456074191}

{333333333333333333,333333333333333333,333333333333333333}

Returns: "Possible"

```
{0}
```
```
{0}
```
```
Returns: "Possible"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.