FastPrep
Problem · Dynamic Programming

Get Distinct Goodness Values

Learn this problem
● HardCitadelINTERNNEW GRADOA

Problem statement

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

getGoodnessValue(arr: int[]) → int[]

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

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.

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 * [4]; goodness = 4 * [2, 4]; goodness = 6 * [3, 4]; goodness = 7

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 ≤ 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]
checking account