898. Bitwise ORs of Subarrays

LeetCode medium original: C# #array #bit-manipulation #csharp #hash-table #leetcode #medium

Task text is translated from Russian for the selected interface language. Code is left unchanged.

LeetCode Static

Если задан integer array arr, return количество различных побитовых ИЛИ всех непустых подarrayов arr. Побитовое ИЛИ подarrayа - это побитовое ИЛИ каждого целого числа в подarrayе. Побитовым ИЛИ подarrayа одного целого числа является это integer. Подarray - это непрерывная непустая последовательность elementов в arrayе.

Example:

Input: arr = [0]

Output: 1

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int SubarrayBitwiseORs(int[] arr) {
        HashSet<int> result = new HashSet<int>();
        HashSet<int> current = new HashSet<int>();
        foreach (int num in arr) {
            HashSet<int> next = new HashSet<int> { num };
            foreach (int x in current) {
                next.Add(x | num);
            }
            current = next;
            result.UnionWith(current);
        }
        return result.Count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int SubarrayBitwiseORs(vector<int>& arr) {
        HashSet<int> result = new HashSet<int>();
        HashSet<int> current = new HashSet<int>();
        foreach (int num in arr) {
            HashSet<int> next = new HashSet<int> { num };
            foreach (int x in current) {
                next.push_back(x | num);
            }
            current = next;
            result.UnionWith(current);
        }
        return result.size();
    }
}

Java solution

matched/original

import java.util.*;

class Solution {
    public int subarrayBitwiseORs(int[] arr) {
        Set<Integer> result = new HashSet<>();
        Set<Integer> current = new HashSet<>();
        for (int num : arr) {
            Set<Integer> next = new HashSet<>();
            for (int x : current) {
                next.add(x | num);
            }
            next.add(num);
            current = next;
            result.addAll(current);
        }
        return result.size();
    }
}

JavaScript solution

matched/original

var subarrayBitwiseORs = function(arr) {
    let result = new Set();
    let current = new Set();
    for (let num of arr) {
        let next = new Set();
        for (let x of current) {
            next.add(x | num);
        }
        next.add(num);
        current = next;
        for (let x of current) {
            result.add(x);
        }
    }
    return result.size;
};

Python solution

matched/original

def subarrayBitwiseORs(arr):
    result = set()
    current = set()
    for num in arr:
        current = {num | x for x in current} | {num}
        result.update(current)
    return len(result)

Go solution

matched/original

package main

func subarrayBitwiseORs(arr []int) int {
    result := make(map[int]struct{})
    current := make(map[int]struct{})
    for _, num := range arr {
        next := make(map[int]struct{})
        next[num] = struct{}{}
        for x := range current {
            next[x|num] = struct{}{}
        }
        current = next
        for x := range current {
            result[x] = struct{}{}
        }
    }
    return len(result)
}

Algorithm

Создать множество для хранения уникальных результатов побитового ИЛИ.

Для каждого elementа arrayа, вычислить побитовое ИЛИ всех подarrayов, начинающихся с этого elementа.

Добавить результат каждого вычисления в множество.

Вернуть размер множества.

😎

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.