Dar una array de enteros positivos. La tarea es encontrar la suma total después de realizar la operación OR bit a bit en todas las subarreglas de la array dada.
Ejemplos:
Input : arr[] = {1, 2, 3, 4, 5}
Output : 71
Input : arr[] = {6, 5, 4, 3, 2}
Output : 84
Explicación :
Enfoque simple : un enfoque simple es encontrar el OR bit a bit de cada subarreglo del arreglo dado usando dos bucles anidados y luego encontrar la suma total. La complejidad temporal de este enfoque será O(N 2 ).
Enfoque eficiente :
- Observe aquí que si un elemento de la array establece un bit, entonces todos los subarreglos que tengan ese elemento tendrán ese bit establecido. Por lo tanto, cuando calculamos la suma de todos los subarreglos que tienen ese número, podemos multiplicar directamente el número de subarreglos por el valor que está generando ese bit.
- Ahora, para hacer esto, una forma sencilla será calcular el número de subarreglos para los que no se ha establecido un bit y restarlo del número total de subarreglos.
Veamos un ejemplo:
Sea el arreglo A = [1, 2, 3, 4, 5] . Ahora el primer bit no está configurado en los elementos 2 y 4 y el número total de dichos subarreglos para los que Bitwise-OR no tendrá el primer bit configurado será 2.
Por lo tanto, el número total de subarreglos para los que Bitwise-OR tendrá El primer bit establecido será: 15-2 = 13.
Por lo tanto, sumaremos (13 * pow(2, 0)) a la suma.
A continuación se muestra la implementación del enfoque anterior:
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
// 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 *
($cnt + 1) / 2);
$cnt = 1;
}
}
// For last element of vec
$cntSubarrNotSet += (int)($cnt *
($cnt + 1) / 2);
// If vec is empty then cntSubarrNotSet
// should be 0 and not 1
if (count($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
$A = array( 1, 2, 3, 4, 5 );
$n = count($A);
echo givesum($A, $n);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript 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
let max = Number.MIN_VALUE;
for(let i = 0; i < A.length; i++)
{
max = Math.max(max, A[i]);
}
// Find the max bit position
// set in the array
let maxBit = Math.ceil(Math.log(max) + 1);
let totalSubarrays = n * (n + 1) / 2;
let s = 0;
// Traverse from 1st bit to last bit which
// can be set in any element of the array
for (let i = 0; i < maxBit; i++) {
// Vector to store indexes of the array
// with i-th bit not set
let vec = [];
// Traverse the array
for (let j = 0; j < n; j++) {
// Check if ith bit is not set in A[j]
let a = A[j] >> i;
if (!(a % 2 == 1)) {
vec.push(j);
}
}
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit
// not set
let cntSubarrNotSet = 0;
let cnt = 1;
for (let j = 1; j < vec.length; 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.length == 0)
cntSubarrNotSet = 0;
// Variable to store count of subarrays
// whose bitwise OR will have i-th bit set
let cntSubarrIthSet = totalSubarrays - cntSubarrNotSet;
s += parseInt(cntSubarrIthSet * Math.pow(2, i), 10);
}
return s;
}
let A = [ 1, 2, 3, 4, 5 ];
let n = A.length;
document.write(givesum(A, n));
// This code is contributed by suresh07.
</script>
Producción:
71
Complejidad del tiempo : O(N*logN)
Publicación traducida automáticamente
Artículo escrito por Anjaney Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA