Round 1
Questions: Given an array arr of length n, find all possible distinct values of goodness that can be obtained by choosing any strictly increasing subsequence of the array. Sort the return array in non-decreasing order.
The goodness of a sequence is defined as the bitwise-OR of its elements.
Example: Consider n= 4, arr = [4, 2, 4, 1].
The strictly increasing subsequences which can be chosen to have distinct goodness values are:
- Empty subsequence; goodness = 0
- [1]; goodness = 1
- [2]; goodness = 2
- [4]; goodness = 4
- [2, 4]; goodness = 6
So, the answer is [0, 1, 2, 4, 6], which is sorted in non-decreasing order.
Function Description:
Complete the function getDistinctGoodnessValues in the editor below.
getDistinctGoodnessValues has the following parameter:
int arr[n]: an array of integers
Returns:
int[]: all possible distinct values of goodness
Constraints:
- 1 ≤ n ≤ 10^4
- 1 ≤ arr[i] < 1024
Input Format For Custom Testing: The first line contains an integer, n, the number of elements in arr. Each line i of the n subsequent lines (where 0 ≤ i < n) represents the ith element of the array.
Sample Case 0:
- Input:
4 3 2 4 6
- Output:
0 2 3 4 6 7
- Explanation: Some strictly increasing subsequences that have distinct goodness values are:
- Empty subsequence; goodness = 0
- [2]; goodness = 2
- [3]; goodness = 3
- [4]; goodness = 4
- [2, 4]; goodness = 6
- [3, 4]; goodness = 7
Sample Case 1:
- Input:
4 3 5 5 1
- Output:
0 1 3 5 7
- Explanation: Strictly increasing subsequences that have distinct goodness values are:
- Empty subsequence; goodness = 0
- [1]; goodness = 1
- [3]; goodness = 3
- [5]; goodness = 5
- [3, 5]; goodness = 7
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.