Strange Function

Moderate

0/80

Average time to solve is 50m

Contributed by

0 upvote

Asked in company

Problem statement

Ninja is given an array ‘arr’ of size ‘n’, integer ‘target’ and strange function given below:-

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of the test case contains two integers ‘n’ size of the array and the ‘target’.

The second line contains ‘n’ space integers denoting the elements of the array.

Output Format:

For each test case, return the minimum possible value of | func(arr, l, r) - 
target |. 

The output for each test case is printed in a 
separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= 'T’ <= 10
1 <= n <= 1000
1 <= target <= 10^9
1 <= arr[i] <= 10^6

Where ‘i’ varies from 1 to ‘n’ where ‘n’ is the length of the array.

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

4
1

Sample Output Explanation:

For the first test case the possible values for all values of l and r for which r >= l.

(1,1) -> 1 & 1 = 1
(1,2) -> 1 & 2 = 0
(1,3) -> 1 & 2 & 3 = 0
(1,4) -> 1 & 2 & 3 & 3 = 0
(2,2) -> 2 & 2 = 2
(2,3) -> 2 & 3 = 2
(2,4) -> 2 & 3 & 3 = 2
(3,3) -> 3 & 3 = 3
(3,4) -> 3 & 3 = 3

Thus 3 will give minimum value for | func(arr,l,r) - target |. Hence ans is | 3 - 7 | = 4.

We can verify that 4 is the minimum possible answer for all other values of ‘l’ and ‘r’


For the second test case the possible values for all values of l and r.

(1,1) -> 2 & 2 = 2
(1,2) -> 2 & 4 = 0
(1,3) -> 2 & 4 & 8 = 0
(1,4) -> 2 & 4 & 8 & 16 = 0
(2,2) -> 4 & 4 = 4
(2,3) -> 4 & 8 = 0
(2,4) -> 4 & 8 & 16 = 0
(3,3) -> 8 & 8 = 8
(3,4) -> 8 & 16 = 0
(4,4) -> 16 & 16 = 16

Thus 4 will give minimum value for | func(arr, l, r) - target |. Hence ans is | 4- 5 |=1

Sample Input 2:

2
7 6
4 2 5 1 4 5 2 
5 4
2 4 4 2 4

Sample Output 2:

1
0

Hint 1

Hint 2

Find the bitwise AND of all subarrays of the array.

Approaches (2)

Approach 1

Approach 2

Brute Force Approach

The main idea is that we need to choose l and r in such a way that ‘R’ >= ‘L’. Hence find the bitwise AND of all subarrays of the given array and find the minimum value of this ‘| func( ‘ARR’ , ‘L’ , ‘R’ ) - target |’ using the bitwise AND of all subarrays of the given array.

Below is the algorithm:

Initialize the ‘ANS’ with target
Run a loop from ‘i’ = 0 to ‘N’ :
- Create a ‘TEMP’ variable equal to ‘ARR[ i ]’.
- Run a loop from ‘j’ = ‘i’ to ‘N’ :
  - Do the AND of ‘TEMP’ and ‘ARR[ j ]’. If ‘| TEMP - TARGET |’ is less than ‘ANS’ then replace ‘ANS’ with ‘| TEMP - TARGET |’.
In the end, return the ‘ANS’.

Time Complexity

O(N^2) where ‘N’ is the size of the array.

We are finding bitwise AND of all subarrays which takes N^2 steps and so, the overall space complexity is O(N^2).

Space Complexity

O(1)

Constant extra space is required and so, the overall space complexity is O(1).

(100% EXP penalty)

Strange Function

Console