FastPrep
Problem · Dynamic Programming

Get Distinct Goodness Values

Learn this problem
● HardCitadel logoCitadelOA

Problem statement

A coding competition organized to hire software developers 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

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

Complete the function getDistinctGoodnessValues in the editor below.

getDistinctGoodnessValues has the following parameter:

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

Returns

int[]: all possible distinct values of goodness

Examples

Example 1

arr = [4, 2, 4, 1]return = [0, 1, 2, 4, 6]

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
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 chosen to have distinct goodness values are:

  • Empty subsequence; goodness = 0
  • [2]; goodness = 2
  • [3]; goodness = 3
  • [4]; goodness = 4
  • [6]; goodness = 6
  • (3, 4); goodness = 7
There are no other strictly increasing subsequences that yield a different goodness value. So, the answer is [0, 2, 3, 4, 6, 7], which is sorted in non-decreasing order.

Example 3

arr = [3, 5, 5, 5, 1]return = [0, 1, 3, 5, 7]

The strictly increasing subsequences which can be chosen to have distinct goodness values are:

  • Empty subsequence; goodness = 0
  • [1]; goodness = 1
  • [3]; goodness = 3
  • [5]; goodness = 5
  • (3, 5); goodness = 7
There are no other strictly increasing subsequences that yield a different goodness value. So, the answer is [0, 1, 3, 5, 7], which is sorted in non-decreasing order.

More Citadel problems

drafts saved locally
public int[] getDistinctGoodnessValues(int[] arr) {
    // write your code here
}
arr[4, 2, 4, 1]
expected[0, 1, 2, 4, 6]
checking account