FastPrep
Problem · Dynamic Programming

Get Distinct Goodness Values

● HardCitadelINTERNNEW GRADOA

A coding competition organized to hire software engineers includes an interesting problem on Bitwise-OR.

The goodness of a sequence is defined as the bitwise-OR of its elements. 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.

Note: A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.

Function Description

Complete the function getGoodnessValue in the editor.

getGoodnessValue has the following parameters:

  1. int arr[n]: an array of integers

Returns

int[]: all possible distinct values of goodness

🌷 Aura Man the slayer 🙌

Examples
01 · Example 1
arr = [4, 2, 4, 1]
return = [0, 1, 2, 4, 6]
The strictly increasing subsequences which can be choosen to have distinct goodness values are: * Empty subsequence; goodness = 0 * [1]; goodness = 1 * [2]; goodness = 2 * [4]; goodness = 4 * [2, 4]; goodness = 6 There are no other strictly increasing subsequences that yield a different goodness value. So, the answer is [0, 1, 2, 4, 6], which is sorted in non-decreasing order.
02 · Example 2
arr = [3, 2, 4, 6]
return = [0, 2, 3, 4, 6, 7]
The strictly increasing subsequences which can be choosen to have distinct goodness values are: * Empty subsequence; goodness = 0 * [2]; goodness = 2 * [3]; goodness = 3 * [2, 4]; goodness = 6 * [3, 4]; goodness = 7
03 · Example 3
arr = [3, 5, 5, 1]
return = [0, 1, 3, 5, 7]
Given n = 4, arr = [3, 5, 5, 1] 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
Constraints
  • 1 ≤ n, m ≤ 10^4
  • 1 <= arr[i] < 1024
More Citadel problems
drafts saved locally
public int[] getGoodnessValue(int[] arr) {
  // write your code here
}
arr[4, 2, 4, 1]
expected[0, 1, 2, 4, 6]
sign in to submit