Last Updated: 4 Apr, 2021
Strange Function
Moderate
Asked in company
Ninja is given an array ‘arr’ of size ‘n’, integer ‘target’ and strange function given below:-
Ninja wants to find two integers ‘l’ and ‘r’ in such a way that '| func(arr, l, r) - target |' will give minimum value. '| |' returns the absolute value of a number. Help Ninja in finding the minimum possible value of | func(arr, l, r) - target |.
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
Approaches
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’.
The main idea is that AND for subarray ‘ANS'( i , j )’ can also be written as ‘ANS( i , j - 1 )’ & ‘ARR[j]’. If at the jth step we have answer for all ‘ANS( 1, j -1)’, ‘ANS( 2 , j - 1 )’... ‘ANS( j - 1 , j - 1)’ then we can find the 'ANS' for 'ANS( i , j )’ using this 'ANS( i , j - 1)’ & ‘ARR[j]’.
The distinct values of ‘ANS( 1, j - 1 )’ , ‘ANS( 2 , j - 1)’ … ‘ANS( j - 1 , j - 1)’ is atmost 32(Since there 32 bits in int) as AND is a decreasing function ‘ANS( 1 , j - 1 )’ , ‘ANS( 2 , j - 1 )... ‘ANS(j - 1, j - 1)’ is decreasing in the way that any two adjacent values that are different have more 1’s in its binary representation.So atmost 32 values can be distinct.
Algorithm:-
- Initialize the 'ANS' with the 'TARGET'.
- Create an unordered set 'PREV' initially empty.
- Run a loop from i=0 to n.
- Create an unordered set 'CURR' with an initial value in it ‘ARR[ i ]’.
- Iterate through all values of 'PREV' with iterator 'ITR' and insert ( 'ITR' & ‘ARR[ i ]’ ).
- Iterate through all values of 'CURR' with iterator 'ITR' and check if | 'ITR' - 'TARGET' | is less than 'ANS' then replace 'ANS' with | 'ITR' - 'TARGET' |.
- After this make 'PREV' = 'CURR'.
- Return the 'ANS' in the end.
Similar problems