Salesforce OA-3 2023

Problem Description

After defeating Dr. Eggman, Sonic the Hedgehog has returned to the Green Hill Zone. The forest critters make him the de facto king for his victory. However, the oxygen levels in the zone are unstable, and Sonic needs to evacuate his subjects to a safe area as soon as possible. Green Hill Zone is linear in geography, with each neighborhood having an oxygen value denoted by O.

The oxygen value for a range of neighborhoods [l, r] (inclusive) is calculated as the bitwise AND of all the oxygen levels between neighborhoods l and r. Mathematically, this is represented as:

Where O[l, r] is the result of the bitwise AND operation applied to all values O_i from index l to r.

Sonic has set a safe target oxygen value T, and your task is to help Tails prepare by finding the safest range of neighborhoods where the absolute difference between the oxygen value of that range and the target value T ) is minimized.

Find the minimum possible value of |O[l, r] - T|, where l <= r.

Input Format:

• The first line contains an integer N, representing the number of neighborhoods in Green Hill Zone.
• The next N lines contain the oxygen level O for each neighborhood.
• The last line contains the target oxygen value T.

Output Format:

• Output an integer representing the minimum possible value of |O[l, r] - T|.

Constraints:

• 1 <= N <= 10^5
• 1 <= O_i <= 10^5
• 0 < T < 10^7

Sample Testcase:

Input:

4
9
12
3
7
5

Output:

2

Explanation:

All possible pairs of [l, r] are: ([0, 0], [1, 1], [2, 2], [3, 3], [0, 1], [1, 2], [2, 3], [0, 2], [1, 3], [0, 3]).

For each pair [l, r], the resulting values of O[l, r] (bitwise AND) are: ([9, 12, 3, 7, 8, 0, 3, 0, 3, 0]).

The value closest to T = 5 is 3 (or 7), and the difference is 2.