Find unique or combination for given array

Question

I have an array of numbers of size n, select all possible distinct increasing subsequence of the array, for each subsequence find the bitwise OR value and return them as result in increasing order.

Example:

arr= [4,2,4,1], n = 4

Result

[1,2,4,6]

Explanation:

All possible distinct increasing subsequences are:
[4]
[2]
[2, 4]
[1]

Bit wise or values are:
[4]
[2]
[2 | 4] = [6]
[1]

So values are [2,4,6, 1]
sorted result is [1,2,4,6]

Another Example:

arr = [3,2,4,6], n = 4

Result

[2,3,4,6,7]

Explanation:

All increasing subsequences and corresponding bitwise or values are:
[3] : 3
[3, 4] : 7
[3, 4, 6] : 7
[3, 6] : 7
[2] : 2
[2, 4] : 6
[2, 4, 6] : 6
[2, 6] : 6
[4] : 4
[4, 6] : 6
[6] : 6

So distinct values are [3,7,2,6,4]
sorted result is [2,3,4,6,7]

Constraints:

1 <= n <= 10^4
1 <= arr[i] <= 1024

I have solved it using brute force approach, here is my code:

import java.util.*;

public class Main {

    public static void main(String[] args) {
        int[] arr = {3,2,4,6};

        List<List<Integer>> subsequences = findIncreasingSubsequences(arr);

        Set<Integer> set = new TreeSet<>();
        for (List<Integer> subsequence : subsequences) {
            int or = subsequence.get(0);
            for(int i=1; i<subsequence.size(); i++) {
                or |= subsequence.get(i);
            }
            //System.out.println(subsequence + " : "+ or);
            set.add(or);
        }
        System.out.println("Result : " + set);
    }

    public static List<List<Integer>> findIncreasingSubsequences(int[] arr) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();

        findSubsequences(arr, result, current, 0);

        return result;
    }

    private static void findSubsequences(int[] arr, List<List<Integer>> result, List<Integer> current, int start) {
        if (!current.isEmpty()) {
            result.add(new ArrayList<>(current)); // Add current subsequence to result
        }

        for (int i = start; i < arr.length; i++) {
            if (current.isEmpty() || arr[i] > current.get(current.size() - 1)) {
                current.add(arr[i]);
                findSubsequences(arr, result, current, i + 1);
                current.remove(current.size() - 1);
            }
        }
    }
}

How to solve this in less time complexity.

Answer 1

Since all array elements are between 1 and 1024 (2¹⁰), the maximum bitwise OR value is 2047. This problem can then be solved in O(2047N) with dynamic programming. For each possible bitwise OR value, maintain the minimum possible value a subsequence with this bitwise OR value could end with (in order to allow as many increasing subsequences as possible).

public static List<Integer> solve(int... nums) {
    final int MAX_VAL = 1024, MAX_OR = MAX_VAL | MAX_VAL - 1;
    var minEndVal = new int[MAX_OR + 1];
    for (int i = 1; i <= MAX_OR; i++) minEndVal[i] = MAX_VAL + 1;
    for (int num : nums)
        for (int i = 0; i < MAX_OR; i++)
            if (minEndVal[i] < num)
                minEndVal[i | num] = Math.min(minEndVal[i | num], num);
    return IntStream.rangeClosed(1, MAX_OR).filter(i -> minEndVal[i] <= MAX_VAL).boxed().toList();
}

Answer 2

I think you can't get away without trying out all possible combinations. But surely you can prune out a lot of branches if those branches would not yield a new result.

Here is my code. I have similar approach as yours, but I didn't really calculate all the combinations, instead just passed what the or'ed value of those current combination is. And pruning on is done if taking the next element would not get you a new or'ed value that you have seen before.

import java.util.*;
 
class Solution {
    void solve(List<Integer> nums, int index, int lastIndex, int taken, int curr, Set<Integer> values) {
        if (taken > 0) {
            values.add(curr);
        }
        if (index >= nums.size()) {
            return;
        }
 
        // Take it.
        if (lastIndex == -1 || nums.get(index) > nums.get(lastIndex)) {
            int newOrValue = curr | nums.get(index);
            if (!values.contains(newOrValue)) {
                solve(nums, index + 1, index, taken + 1, newOrValue, values);
            }
        }
        // Leave it
        solve(nums, index + 1, lastIndex, taken, curr, values);
    }
 
    public List<Integer> getIncreasingSubsequenceOrValues(List<Integer> nums) {
        Set<Integer> values = new HashSet<>();
        solve(nums, 0 /* index */, -1 /* lastIndex */, 0 /* taken */, 0 /* curr */, values);
        return new ArrayList<>(values);
    }
}
 
public class Main {
    static void print(List<Integer> v) {
        for (int el : v) {
            System.out.print(el + " ");
        }
        System.out.println();
    }
 
    static void test(List<Integer> nums) {
        System.out.print("Testing for array: ");
        print(nums);
 
        Solution solution = new Solution();
        List<Integer> result = solution.getIncreasingSubsequenceOrValues(nums);
 
        print(result);
    }
 
    public static void main(String[] args) {
        test(Arrays.asList(4, 2, 4, 1));
        test(Arrays.asList(3, 2, 4, 6));
    }
}

Runnable at: https://ideone.com/NmfuVV