Prefix sum problems: Bitwise OR of sum of all subsequence of the array

Problem Statement:

You are given an array, you need to find the bitwise or of sum of all the sub sequence of the array.

Example:

Input: arr [] = [1, 2, 3] 
Output: 7

Explanation: 
Sumsequence are:

[1] = 1
[2] = 2
[3] = 3
[1, 2] = 3
[2, 3] = 5
[1, 3] = 4
[1, 2, 3] = 6

Sum = 1 | 2 | 3 | 3 | 5 |4 | 6  = 7

Solution Explanation:

Solution is very simple.

As we are doing OR operation, the set bits in the array elements will also be set in the final result.

Set bits in the prefix sum array will also be set in the final result.

So for that, iterate over the array and at any instance:

Calculate prefixSum = prefixSum + arr[i]
Calculate result as result = result | arr[i] | prefixSum

Return the result at the end of the array

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

using namespace std;


int solution(vector<int>& nums) 
{

    int prefix_sum = 0;

    int result = 0;

    for (int i = 0; i < nums.size(); i++) 
    {

        prefix_sum += nums[i];

        result |= prefix_sum;
    }

    return result;
}

int main()
{
    vector<int> arr =  {1, 2, 3};
  
    cout << solution(arr)<<endl;
    
    return 0;
}

Output
————-

7