Сумма побитового ИЛИ всех подмассивов данного массива | Комплект 2
Дайте массив положительных целых чисел. Задача состоит в том, чтобы найти общую сумму после выполнения побитовой операции ИЛИ для всех подмассивов данного массива.
Примеры:
Ввод : arr [] = {1, 2, 3, 4, 5} Выход : 71 Ввод : arr [] = {6, 5, 4, 3, 2} Выход : 84
Пояснение :
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Простой подход : простой подход состоит в том, чтобы найти побитовое ИЛИ для каждого подмассива данного массива с помощью двух вложенных циклов, а затем найти общую сумму. Временная сложность этого подхода будет O (N 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 * (
|