Сумма побитового ИЛИ всех подмассивов данного массива | Комплект 2

Опубликовано: 5 Января, 2022

Дайте массив положительных целых чисел. Задача состоит в том, чтобы найти общую сумму после выполнения побитовой операции ИЛИ для всех подмассивов данного массива.

Примеры:

Ввод : arr [] = {1, 2, 3, 4, 5}
Выход : 71

Ввод : arr [] = {6, 5, 4, 3, 2}
Выход : 84

Пояснение :

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Простой подход : простой подход состоит в том, чтобы найти побитовое ИЛИ для каждого подмассива данного массива с помощью двух вложенных циклов, а затем найти общую сумму. Временная сложность этого подхода будет O (N 2 ).

Эффективный подход :

  1. Обратите внимание, что если бит устанавливается элементом массива, то для всех подмассивов, содержащих этот элемент, этот бит будет установлен. Поэтому, когда мы вычисляем сумму всех подмассивов, имеющих это число, мы можем напрямую умножить количество подмассивов на значение, которое создает бит.
  2. Теперь, чтобы сделать это, проще всего будет вычислить количество подмассивов, для которых бит не установлен, и вычесть его из общего количества подмассивов.

Посмотрим на пример:
Пусть массив A = [1, 2, 3, 4, 5] . Теперь 1-й бит не установлен в элементах 2 и 4, и общее количество таких подмассивов, для которых побитовое ИЛИ не будет иметь установленный 1-й бит, будет равно 2.

Следовательно, общее количество подмассивов, для которых в операции поразрядного ИЛИ будет установлен 1-й бит, будет: 15-2 = 13.

Поэтому мы добавим (13 * pow (2, 0)) к сумме.

Ниже представлена реализация описанного выше подхода:

C ++

// C++ program to find sum of bitwise OR
// of all subarrays
#include <bits/stdc++.h>
using namespace std;
// Function to find sum of bitwise OR
// of all subarrays
int givesum( int A[], int n)
{
// Find max element of the array
int max = *max_element(A, A + n);
// Find the max bit position set in
// the array
int maxBit = log2(max) + 1;
int totalSubarrays = n * (n + 1) / 2;
int s = 0;
// Traverse from 1st bit to last bit which
// can be set in any element of the array
for ( int i = 0; i < maxBit; i++) {
int c1 = 0;
// Vector to store indexes of the array
// with i-th bit not set
vector< int > vec;
int sum = 0;
// Traverse the array
for ( int j = 0; j < n; j++) {
// Check if ith bit is not set in A[j]
int a = A[j] >> i;
if (!(a & 1)) {
vec.push_back(j);
}
}
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit
// not set
int cntSubarrNotSet = 0;
int cnt = 1;
for ( int j = 1; j < vec.size(); j++) {
if (vec[j] - vec[j - 1] == 1) {
cnt++;
}
else {
cntSubarrNotSet += cnt * (cnt + 1) / 2;
cnt = 1;
}
}
// For last element of vec
cntSubarrNotSet += cnt * (cnt + 1) / 2;
// If vec is empty then cntSubarrNotSet
// should be 0 and not 1
if (vec.size() == 0)
cntSubarrNotSet = 0;
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit set
int cntSubarrIthSet = totalSubarrays - cntSubarrNotSet;
s += cntSubarrIthSet * pow (2, i);
}
return s;
}
// Driver code
int main()
{
int A[] = { 1, 2, 3, 4, 5 };
int n = sizeof (A) / sizeof (A[0]);
cout << givesum(A, n);
return 0;
}

Джава

// Java program to find sum of bitwise OR
// of all subarrays
import java.util.*;
class GFG {
// Function to find sum of bitwise OR
// of all subarrays
static int givesum( int A[], int n)
{
// Find max element of the array
int max = Arrays.stream(A).max().getAsInt();
// Find the max bit position
// set in the array
int maxBit = ( int )Math.ceil(Math.log(max) + 1 );
int totalSubarrays = n * (n + 1 ) / 2 ;
int s = 0 ;
// Traverse from 1st bit to last bit which
// can be set in any element of the array
for ( int i = 0 ; i < maxBit; i++) {
int c1 = 0 ;
// Vector to store indexes of the array
// with i-th bit not set
Vector<Integer> vec = new Vector<>();
int sum = 0 ;
// Traverse the array
for ( int j = 0 ; j < n; j++) {
// Check if ith bit is not set in A[j]
int a = A[j] >> i;
if (!(a % 2 == 1 )) {
vec.add(j);
}
}
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit
// not set
int cntSubarrNotSet = 0 ;
int cnt = 1 ;
for ( int j = 1 ; j < vec.size(); j++) {
if (vec.get(j) - vec.get(j - 1 ) == 1 ) {
cnt++;
}
else {
cntSubarrNotSet += cnt * (cnt + 1 ) / 2 ;
cnt = 1 ;
}
}
// For last element of vec
cntSubarrNotSet += cnt * (cnt + 1 ) / 2 ;
// If vec is empty then cntSubarrNotSet
// should be 0 and not 1
if (vec.size() == 0 )
cntSubarrNotSet = 0 ;
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit set
int cntSubarrIthSet = totalSubarrays - cntSubarrNotSet;
s += cntSubarrIthSet * Math.pow( 2 , i);
}
return s;
}
// Driver code
public static void main(String[] args)
{
int A[] = { 1 , 2 , 3 , 4 , 5 };
int n = A.length;
System.out.println(givesum(A, n));
}
}
// This code is contributed by 29AjayKumar

Python3

# Python 3 program to find sum of
# bitwise OR of all subarrays
# from math lib. import log2 function
from math import log2
# Function to find sum of bitwise OR
# of all subarrays
def givesum(A, n) :
# Find max element of the array
max_element = max (A)
# Find the max bit position set in
# the array
maxBit = int (log2(max_element)) + 1
totalSubarrays = n * (n + 1 ) / / 2
s = 0
# Traverse from 1st bit to last bit which
# can be set in any element of the array
for i in range (maxBit) :
c1 = 0
# List to store indexes of the array
# with i-th bit not set
vec = []
sum = 0
# Traverse the array
for j in range (n) :
# Check if ith bit is not set in A[j]
a = A[j] >> i
if ( not (a & 1 )) :
vec.append(j)
# Variable to store count of subarrays
# whose bitwise OR will have i-th bit
# not set
cntSubarrNotSet = 0
cnt = 1
for j in range ( 1 , len (vec)) :
if (vec[j] - vec[j - 1 ] = = 1 ) :
cnt + = 1
else :
cntSubarrNotSet + = cnt * (cnt + 1 ) / / 2
cnt = 1
# For last element of vec
cntSubarrNotSet + = cnt * (cnt + 1 ) / / 2
# If vec is empty then cntSubarrNotSet
# should be 0 and not 1
if len (vec) = = 0 :
cntSubarrNotSet = 0
# Variable to store count of subarrays
# whose bitwise OR will have i-th bit set
cntSubarrIthSet = totalSubarrays - cntSubarrNotSet
s + = cntSubarrIthSet * pow ( 2 , i)
return s
# Driver code
if __name__ = = "__main__" :
A = [ 1 , 2 , 3 , 4 , 5 ]
n = len (A)
print (givesum(A, n))
# This code is contributed by Ryuga

C #

// C# program to find sum of bitwise OR
// of all subarrays
using System;
using System.Linq;
using System.Collections.Generic;
class GFG {
// Function to find sum of bitwise OR
// of all subarrays
static int givesum( int [] A, int n)
{
// Find max element of the array
int max = A.Max();
// Find the max bit position
// set in the array
int maxBit = ( int )Math.Ceiling(Math.Log(max) + 1);
int totalSubarrays = n * (n + 1) / 2;
int s = 0;
// Traverse from 1st bit to last bit which
// can be set in any element of the array
for ( int i = 0; i < maxBit; i++) {
// Vector to store indexes of the array
// with i-th bit not set
List< int > vec = new List< int >();
// Traverse the array
for ( int j = 0; j < n; j++) {
// Check if ith bit is not set in A[j]
int a = A[j] >> i;
if (!(a % 2 == 1)) {
vec.Add(j);
}
}
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit
// not set
int cntSubarrNotSet = 0;
int cnt = 1;
for ( int j = 1; j < vec.Count; j++) {
if (vec[j] - vec[j - 1] == 1) {
cnt++;
}
else {
cntSubarrNotSet += cnt * (cnt + 1) / 2;
cnt = 1;
}
}
// For last element of vec
cntSubarrNotSet += cnt * (cnt + 1) / 2;
// If vec is empty then cntSubarrNotSet
// should be 0 and not 1
if (vec.Count() == 0)
cntSubarrNotSet = 0;
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit set
int cntSubarrIthSet = totalSubarrays - cntSubarrNotSet;
s += ( int )(cntSubarrIthSet * Math.Pow(2, i));
}
return s;
}
// Driver code
public static void Main()
{
int [] A = { 1, 2, 3, 4, 5 };
int n = A.Length;
Console.WriteLine(givesum(A, n));
}
}
/* This code contributed by PrinciRaj1992 */

PHP

<?php
// PHP program to find sum of bitwise OR
// of all subarrays
// Function to find sum of bitwise OR
// of all subarrays
function givesum( $A , $n )
{
// Find max element of the array
$max = max( $A );
// Find the max bit position set in
// the array
$maxBit = (int)((log( $max ) /
log10(2)) + 1);
$totalSubarrays = (int)( $n * ( $n + 1) / 2);
$s = 0;
// Traverse from 1st bit to last bit which
// can be set in any element of the array
for ( $i = 0; $i < $maxBit ; $i ++)
{
$c1 = 0;
// Vector to store indexes of
// the array with i-th bit not set
$vec = array ();
$sum = 0;
// Traverse the array
for ( $j = 0; $j < $n ; $j ++)
{
// Check if ith bit is
// not set in A[j]
$a = $A [ $j ] >> $i ;
if (!( $a & 1))
{
array_push ( $vec , $j );
}
}
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit
// not set
$cntSubarrNotSet = 0;
$cnt = 1;
for ( $j = 1; $j < count ( $vec ); $j ++)
{
if ( $vec [ $j ] - $vec [ $j - 1] == 1)
{
$cnt ++;
}
else
{
$cntSubarrNotSet += (int)( $cnt *