Dada una array arr[] que consiste en N enteros ( Todos los elementos de la array son una potencia perfecta de 2 ), la tarea es calcular la suma de los elementos máximos en todas las subarreglas .
Nota: si la frecuencia del elemento máximo en un subarreglo es par, agregue el doble del valor de ese elemento a la suma.
Ejemplos:
Entrada: arr[] = {1, 2}
Salida: 5
Explicación: Todos los subarreglos posibles son {1}, {1, 2}, {2}.
Subarreglo 1: {1}. Máximo = 1. Suma = 1.
Subarreglo 2: {1, 2}. Máximo = 2. Suma = 3.
Subarreglo 3: {2}. Máximo = 2. Suma = 5.
Por lo tanto, la salida requerida es 5.Entrada: arr[] = {4, 4}
Salida: 16
Explicación: Todos los subarreglos posibles son {4}, {4, 4}, {4}.
Subarreglo 1: {4}. Máximo = 4. Suma = 1.
Subarreglo 2: {4, 4}. Máximo = 4. Dado que el máximo ocurre dos veces en el subarreglo, Suma = 4 + 8 = 12.
Subarreglo 3: {4}. Máximo = 4. Suma = 16.
Por lo tanto, la salida requerida es 16.
Enfoque ingenuo: el enfoque más simple para resolver este problema es generar todos los subarreglos posibles del arreglo dado y encontrar el elemento máximo en todos los subarreglos junto con el recuento de sus ocurrencias. Finalmente, imprima la suma de todos los elementos máximos obtenidos. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos sum , para almacenar la suma requerida del máximo de todos los subarreglos.
- Genere todos los subarreglos posibles de la array dada arr[] .
- Para cada subarreglo generado, encuentre la frecuencia del elemento más grande y verifique si la frecuencia es par o no . Si se determina que es cierto, agregue 2 * máximo a la suma . De lo contrario, agregue el máximo a la suma .
- Después de completar los pasos anteriores, imprima el valor de sum como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to calculate sum of
// maximum of all subarrays
void findSum(vector<int>a)
{
// Stores the sum of maximums
int ans = 0;
// Traverse the array
for(int low = 0;
low < a.size();
low++)
{
for(int high = low;
high < a.size();
high++)
{
// Store the frequency of the
// maximum element in subarray
int count = 0;
int maxNumber = 0;
// Finding maximum
for(int i = low;
i <= high; i++)
{
// Increment frequency by 1
if (a[i] == maxNumber)
count++;
// If new maximum is obtained
else if (a[i] > maxNumber)
{
maxNumber = a[i];
count = 1;
}
}
// If frequency of maximum
// is even, then add 2*maxNumber.
// Otherwise, add maxNumber
ans += maxNumber * ((count % 2 == 0) ? 2 : 1);
}
}
// Print the sum obtained
cout << (ans);
}
// Driver Code
int main()
{
vector<int>arr = { 2, 1, 4, 4, 2 };
// Function Call
findSum(arr);
}
// This code is contributed by amreshkumar3
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate sum of
// maximum of all subarrays
public static void findSum(int a[])
{
// Stores the sum of maximums
int ans = 0;
// Traverse the array
for (int low = 0;
low < a.length; low++) {
for (int high = low;
high < a.length;
high++) {
// Store the frequency of the
// maximum element in subarray
int count = 0;
int maxNumber = 0;
// Finding maximum
for (int i = low;
i <= high; i++) {
// Increment frequency by 1
if (a[i] == maxNumber)
count++;
// If new maximum is obtained
else if (a[i] > maxNumber) {
maxNumber = a[i];
count = 1;
}
}
// If frequency of maximum
// is even, then add 2*maxNumber.
// Otherwise, add maxNumber
ans += maxNumber
* ((count % 2 == 0) ? 2 : 1);
}
}
// Print the sum obtained
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 1, 4, 4, 2 };
// Function Call
findSum(arr);
}
}
Python3
# Python3 program for the above approach # Function to calculate sum of # maximum of all subarrays def findSum(a): # Stores the sum of maximums ans = 0 # Traverse the array for low in range(0, len(a)): for high in range(low,len(a)): # Store the frequency of the # maximum element in subarray count = 0 maxNumber = 0 # Finding maximum for i in range(low, high + 1): # Increment frequency by 1 if (a[i] == maxNumber): count += 1 # If new maximum is obtained elif (a[i] > maxNumber): maxNumber = a[i] count = 1 # If frequency of maximum # is even, then add 2*maxNumber. # Otherwise, add maxNumber if count % 2: ans += maxNumber else: ans += maxNumber * 2 # Print the sum obtained print(ans) # Driver Code arr = [ 2, 1, 4, 4, 2 ] # Function Call findSum(arr) # This code is contributed by rohitsingh07052
C#
// C# program for the above approach
using System;
class GFG {
// Function to calculate sum of
// maximum of all subarrays
public static void findSum(int[] a)
{
// Stores the sum of maximums
int ans = 0;
// Traverse the array
for (int low = 0; low < a.Length; low++) {
for (int high = low; high < a.Length; high++) {
// Store the frequency of the
// maximum element in subarray
int count = 0;
int maxNumber = 0;
// Finding maximum
for (int i = low; i <= high; i++) {
// Increment frequency by 1
if (a[i] == maxNumber)
count++;
// If new maximum is obtained
else if (a[i] > maxNumber) {
maxNumber = a[i];
count = 1;
}
}
// If frequency of maximum
// is even, then add 2*maxNumber.
// Otherwise, add maxNumber
ans += maxNumber
* ((count % 2 == 0) ? 2 : 1);
}
}
// Print the sum obtained
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
int[] arr = { 2, 1, 4, 4, 2 };
// Function Call
findSum(arr);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to calculate sum of
// maximum of all subarrays
function findSum(a) {
// Stores the sum of maximums
var ans = 0;
// Traverse the array
for (var low = 0; low < a.length; low++) {
for (var high = low; high < a.length; high++) {
// Store the frequency of the
// maximum element in subarray
var count = 0;
var maxNumber = 0;
// Finding maximum
for (var i = low; i <= high; i++) {
// Increment frequency by 1
if (a[i] === maxNumber) count++;
// If new maximum is obtained
else if (a[i] > maxNumber) {
maxNumber = a[i];
count = 1;
}
}
// If frequency of maximum
// is even, then add 2*maxNumber.
// Otherwise, add maxNumber
ans += maxNumber * (count % 2 === 0 ? 2 : 1);
}
}
// Print the sum obtained
document.write(ans);
}
// Driver Code
var arr = [2, 1, 4, 4, 2];
// Function Call
findSum(arr);
</script>
Producción:
75
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque optimizado: para optimizar el enfoque anterior, la idea es almacenar las sumas de prefijos de cada bit de los elementos del arreglo y encontrar la frecuencia del elemento más grande en un subarreglo en complejidad computacional O(1) . Este enfoque funciona ya que todos los elementos de la array son potencias de 2 .
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the maximum
// in subarray {arr[low], ..., arr[high]}
int getCountLargestNumber(
int low, int high, int i,
vector<vector<int>> prefixSums);
// Function to calculate the prefix
// sum array
vector<vector<int>> getPrefixSums(
vector<int> a);
// Function to calculate sum of
// maximum of all subarrays
void findSum(vector<int> a)
{
// Calculate prefix sum array
vector<vector<int>> prefixSums
= getPrefixSums(a);
// Store the sum of maximums
int ans = 0;
// Traverse the array
for (int low = 0;
low < a.size();
low++) {
for (int high = low;
high < a.size();
high++) {
// Store the frequency of the
// maximum element in subarray
int count = 0;
int maxNumber = 0;
// Store prefix sum of every bit
for (int i = 30; i >= 0; i--) {
// Get the frequency of the
// largest element in subarray
count = getCountLargestNumber(
low, high, i, prefixSums);
if (count > 0) {
maxNumber = (1 << i);
// If frequency of the largest
// element is even, add 2 * maxNumber
// Otherwise, add maxNumber
ans += maxNumber
* ((count % 2 == 0) ? 2 : 1);
break;
}
}
}
}
// Print the required answer
cout << ans;
}
// Function to calculate the prefix
// sum array
vector<vector<int>> getPrefixSums(
vector<int> a)
{
// Initialize prefix array
vector<vector<int>> prefix(32, vector<int>(a.size() + 1, 0));
// Start traversing the array
for (int j = 0; j < a.size(); j++) {
// Update the prefix array for
// each element in the array
for (int i = 0; i <= 30; i++) {
// To check which bit is set
int mask = (1 << i);
prefix[i][j + 1] += prefix[i][j];
if ((a[j] & mask) > 0)
prefix[i][j + 1]++;
}
}
// Return prefix array
return prefix;
}
// Function to find the maximum
// in subarray {arr[low], ..., arr[high]}
int getCountLargestNumber(
int low, int high, int i,
vector<vector<int>> prefixSums)
{
return prefixSums[i][high + 1]
- prefixSums[i][low];
}
// Driver Code
int main()
{
vector<int> arr = { 2, 1, 4, 4, 2 };
// Function Call
findSum(arr);
return 0;
}
// This code is contributed
// by Shubham Singh
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate sum of
// maximum of all subarrays
public static void findSum(int a[])
{
// Calculate prefix sum array
int[][] prefixSums
= getPrefixSums(a);
// Store the sum of maximums
int ans = 0;
// Traverse the array
for (int low = 0;
low < a.length;
low++) {
for (int high = low;
high < a.length;
high++) {
// Store the frequency of the
// maximum element in subarray
int count = 0;
int maxNumber = 0;
// Store prefix sum of every bit
for (int i = 30; i >= 0; i--) {
// Get the frequency of the
// largest element in subarray
count = getCountLargestNumber(
low, high, i, prefixSums);
if (count > 0) {
maxNumber = (1 << i);
// If frequency of the largest
// element is even, add 2 * maxNumber
// Otherwise, add maxNumber
ans += maxNumber
* ((count % 2 == 0) ? 2 : 1);
break;
}
}
}
}
// Print the required answer
System.out.println(ans);
}
// Function to calculate the prefix
// sum array
public static int[][] getPrefixSums(
int[] a)
{
// Initialize prefix array
int[][] prefix = new int[32][a.length + 1];
// Start traversing the array
for (int j = 0; j < a.length; j++) {
// Update the prefix array for
// each element in the array
for (int i = 0; i <= 30; i++) {
// To check which bit is set
int mask = (1 << i);
prefix[i][j + 1] += prefix[i][j];
if ((a[j] & mask) > 0)
prefix[i][j + 1]++;
}
}
// Return prefix array
return prefix;
}
// Function to find the maximum
// in subarray {arr[low], ..., arr[high]}
public static int
getCountLargestNumber(
int low, int high, int i,
int[][] prefixSums)
{
return prefixSums[i][high + 1]
- prefixSums[i][low];
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 1, 4, 4, 2 };
// Function Call
findSum(arr);
}
}
Python3
# Python program for the above approach # Function to calculate sum of # maximum of all subarrays def findSum(a): # Calculate prefix sum array prefixSums = getPrefixSums(a); # Store the sum of maximums ans = 1; # Traverse the array for low in range(len(a)): for high in range(len(a)): # Store the frequency of the # maximum element in subarray count = 0; maxNumber = 0; # Store prefix sum of every bit for i in range(30,0,-1): # Get the frequency of the # largest element in subarray count = getCountLargestNumber(low, high, i, prefixSums); if (count > 0): maxNumber = (1 << i); # If frequency of the largest # element is even, add 2 * maxNumber # Otherwise, add maxNumber if(count % 2 == 0): ans += maxNumber * 2; else: ans += maxNumber * 1; break; # Print the required answer print(ans); # Function to calculate the prefix # sum array def getPrefixSums(a): # Initialize prefix array prefix = [[0 for i in range(len(a)+1)] for j in range(32)]; # Start traversing the array for j in range(len(a)): # Update the prefix array for # each element in the array for i in range(31): # To check which bit is set mask = (1 << i); prefix[i][j + 1] += prefix[i][j]; if ((a[j] & mask) > 0): prefix[i][j + 1]+=1; # Return prefix array return prefix; # Function to find the maximum # in subarray:arr[low], ..., arr[high] def getCountLargestNumber(low, high, i, prefixSums): return prefixSums[i][high + 1] - prefixSums[i][low]; # Driver Code if __name__ == '__main__': arr = [ 2, 1, 4, 4, 2 ]; # Function Call findSum(arr); # This code is contributed by gauravrajput1
C#
// C# program for the above approach
using System;
public class GFG {
// Function to calculate sum of
// maximum of all subarrays
public static void findSum(int []a) {
// Calculate prefix sum array
int[,] prefixSums = getPrefixSums(a);
// Store the sum of maximums
int ans = 0;
// Traverse the array
for (int low = 0; low < a.Length; low++) {
for (int high = low; high < a.Length; high++) {
// Store the frequency of the
// maximum element in subarray
int count = 0;
int maxNumber = 0;
// Store prefix sum of every bit
for (int i = 30; i >= 0; i--) {
// Get the frequency of the
// largest element in subarray
count = getCountLargestNumber(low, high, i, prefixSums);
if (count > 0) {
maxNumber = (1 << i);
// If frequency of the largest
// element is even, add 2 * maxNumber
// Otherwise, add maxNumber
ans += maxNumber * ((count % 2 == 0) ? 2 : 1);
break;
}
}
}
}
// Print the required answer
Console.WriteLine(ans);
}
// Function to calculate the prefix
// sum array
public static int[,] getPrefixSums(int[] a) {
// Initialize prefix array
int[,] prefix = new int[32,a.Length + 1];
// Start traversing the array
for (int j = 0; j < a.Length; j++) {
// Update the prefix array for
// each element in the array
for (int i = 0; i <= 30; i++) {
// To check which bit is set
int mask = (1 << i);
prefix[i, j + 1] += prefix[i,j];
if ((a[j] & mask) > 0)
prefix[i, j + 1]++;
}
}
// Return prefix array
return prefix;
}
// Function to find the maximum
// in subarray {arr[low], ..., arr[high]}
public static int getCountLargestNumber(int low, int high, int i, int[,] prefixSums) {
return prefixSums[i,high + 1] - prefixSums[i,low];
}
// Driver Code
public static void Main(String[] args) {
int[] arr = { 2, 1, 4, 4, 2 };
// Function Call
findSum(arr);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program for the above approach
// Function to calculate sum of
// maximum of all subarrays
function findSum(a)
{
// Calculate prefix sum array
var prefixSums = getPrefixSums(a);
// Store the sum of maximums
var ans = 0;
// Traverse the array
for (var low = 0; low < a.length; low++) {
for (var high = low; high < a.length; high++) {
// Store the frequency of the
// maximum element in subarray
var count = 0;
var maxNumber = 0;
// Store prefix sum of every bit
for (var i = 30; i >= 0; i--) {
// Get the frequency of the
// largest element in subarray
count = getCountLargestNumber(low, high, i, prefixSums);
if (count > 0) {
maxNumber = (1 << i);
// If frequency of the largest
// element is even, add 2 * maxNumber
// Otherwise, add maxNumber
ans += maxNumber * ((count % 2 == 0) ? 2 : 1);
break;
}
}
}
}
// Print the required answer
document.write(ans);
}
// Function to calculate the prefix
// sum array
function getPrefixSums(a) {
// Initialize prefix array
var prefix = Array(32).fill().map(()=>Array(a.length + 1).fill(0));
// Start traversing the array
for (var j = 0; j < a.length; j++) {
// Update the prefix array for
// each element in the array
for (var i = 0; i <= 30; i++) {
// To check which bit is set
var mask = (1 << i);
prefix[i][j + 1] += prefix[i][j];
if ((a[j] & mask) > 0)
prefix[i][j + 1]++;
}
}
// Return prefix array
return prefix;
}
// Function to find the maximum
// in subarray {arr[low], ..., arr[high]}
function getCountLargestNumber(low , high , i, prefixSums) {
return prefixSums[i][high + 1] - prefixSums[i][low];
}
// Driver Code
var arr = [ 2, 1, 4, 4, 2 ];
// Function Call
findSum(arr);
// This code is contributed by gauravrajput1
</script>
Producción:
75
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(32 * N)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar la propiedad de que todos los elementos de la array son potencias de 2 y aprovechar esa propiedad para resolver el problema. Siga los pasos a continuación para resolver el problema:
- Iterar a través de todas las potencias de 2 en orden descendente . Considere cualquier potencia arbitraria de 2 como una máscara .
- Divida la array en subarreglos de modo que ningún subarreglo contenga arr[index] = -1 , donde un índice es cualquier posición válida en el arreglo.
- Sea S el subarreglo obtenido del paso anterior . Recorra S y agregue los valores aportados por solo los subarreglos en S , que tienen la máscara actual, desde el bucle externo. También establezca la posición correspondiente, donde arr[index] = mask , a arr[index] = -1 .
- Para calcular los valores aportados por todos los subarreglos en S que contiene la máscara y mantener tres contadores como oddCount , eventCount y la frecuencia de la máscara .
- El puntero anterior apunta al índice anterior, de modo que arr[prev] = mask .
- En cualquier índice , donde arr[índice] = máscara , obtenga el recuento de enteros entre la última aparición de la máscara y la aparición actual restando prev del índice. Use este conteo y la paridad de frecuencia de máscara, para obtener los valores aportados por todos los subarreglos contiguos que contienen una máscara, usando la fórmula conteo = (índice – anterior) y agregue el conteo a la respuesta.
- Si la frecuencia del máximo es par o impar y si la paridad es impar :
- Los valores aportados por todos los subarreglos contiguos que tienen la frecuencia de máscara como impar son (recuento – 1)*parRecuento + imparRecuento .
- Valores aportados por todos los subarreglos contiguos que tienen la frecuencia de máscara como par es 2*(cuenta – 1)*cuentaimpar + 2*cuentapar .
- De lo contrario, si la paridad es par :
- Los valores aportados por todos los subarreglos contiguos que tienen la frecuencia de máscara como impar son (recuento – 1)*recuentoimpar + Recuentopar .
- Valores aportados por todos los subarreglos contiguos que tienen la frecuencia de máscara como par es 2*(cuenta – 1) * cuentaPar + 2 * cuentaimpar .
- Sume todos los valores correspondientes a la respuesta. También agregue el conteo a evenCount si la paridad es par. De lo contrario, agregue count a oddCount .
A continuación se muestra la implementación del enfoque anterior:
Java
// Java program for the above approach
import java.io.*;
class GFG {
// Function to calculate sum of
// maximum of all subarrays
public static void findSum(int a[])
{
int ans = 0;
int prev = -1;
// Iterate over the range [30, 0]
for (int i = 30; i >= 0; i--) {
int mask = (1 << i);
// Inner loop through the
// length of the array
for (int j = 0;
j < a.length; j++) {
// Divide the array such
// that no subarray will
// have any index set to -1
if (a[j] == -1) {
ans += findSumOfValuesOfRange(
a, prev + 1, j - 1, mask);
prev = j;
}
}
// Find the sum of subarray
ans += findSumOfValuesOfRange(
a, prev + 1, a.length - 1, mask);
}
// Print the sum obtained
System.out.println(ans);
}
// Function that takes any subarray
// S and return values contributed
// by only the subarrays in S containing mask
public static int findSumOfValuesOfRange(
int[] a, int low, int high, int mask)
{
if (low > high)
return 0;
// Stores count even, odd count of
// occurrences and maximum element
int evenCount = 0, oddCount = 0,
countLargestNumber = 0;
int prev = low - 1, ans = 0;
// Traverse from low to high
for (int i = low; i <= high; i++) {
// Checking if this position
// in the array is mask
if ((mask & a[i]) > 0) {
// Mask is the largest
// number in subarray.
// Increment count by 1
countLargestNumber++;
// Store parity as 0 or 1
int parity = countLargestNumber % 2;
// Setting a[i]=-1, this
// will help in splitting
// array into subarrays
a[i] = -1;
int count = i - prev;
ans += count;
// Add values contributed
// by those subarrays that
// have an odd frequency
ans += (count - 1)
* ((parity == 1) ? evenCount
: oddCount);
ans += ((parity == 1) ? oddCount
: evenCount);
// Adding values contributed
// by those subarrays that
// have an even frequency
ans += 2 * (count - 1)
* ((parity == 1) ? oddCount
: evenCount);
ans += 2
* ((parity == 1) ? evenCount
: oddCount);
// Set the prev pointer
// to this position
prev = i;
if (parity == 1)
oddCount += count;
else
evenCount += count;
}
}
if (prev != low - 1) {
int count = high - prev;
int parity = countLargestNumber % 2;
ans += count
* ((parity == 1)
? oddCount
: evenCount);
ans += 2 * count
* ((parity == 1)
? evenCount
: oddCount);
ans *= mask;
}
// Return the final sum
return ans;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 2, 1, 4, 4, 2 };
// Function call
findSum(arr);
}
}
Python3
# Python program for the above approach # Function to calculate sum of # maximum of all subarrays def findSum(a): ans = 0 prev = -1 # Iterate over the range [30, 0] for i in range(30,-1,-1): mask = (1 << i) # Inner loop through the # length of the array for j in range(len(a)): # Divide the array such # that no subarray will # have any index set to -1 if (a[j] == -1): ans += findSumOfValuesOfRange(a, prev + 1, j - 1, mask) prev = j # Find the sum of subarray ans += findSumOfValuesOfRange(a, prev + 1, len(a) - 1, mask) # Print the sum obtained print(ans) # Function that takes any subarray # S and return values contributed # by only the subarrays in S containing mask def findSumOfValuesOfRange(a , low , high , mask): if (low > high): return 0 # Stores count even, odd count of # occurrences and maximum element evenCount,oddCount,countLargestNumber = 0,0,0 prev,ans = low - 1,0 # Traverse from low to high for i in range(low,high + 1): # Checking if this position # in the array is mask if ((mask & a[i]) > 0): # Mask is the largest # number in subarray. # Increment count by 1 countLargestNumber += 1 # Store parity as 0 or 1 parity = countLargestNumber % 2 # Setting a[i]=-1, this # will help in splitting # array into subarrays a[i] = -1 count = i - prev ans += count # Add values contributed # by those subarrays that # have an odd frequency ans += (count - 1) * (evenCount if (parity == 1) else oddCount) ans += (oddCount if (parity == 1) else evenCount) # Adding values contributed # by those subarrays that # have an even frequency ans += 2 * (count - 1) * (oddCount if (parity == 1) else evenCount) ans += 2 * (evenCount if (parity == 1) else oddCount) # Set the prev pointer # to this position prev = i if (parity == 1): oddCount += count else: evenCount += count if (prev != low - 1): count = high - prev parity = countLargestNumber % 2 ans += count * (oddCount if (parity == 1) else evenCount) ans += 2 * count * (evenCount if (parity == 1) else oddCount) ans *= mask # Return the final sum return ans # Driver Code arr = [ 2, 1, 4, 4, 2 ] # function call findSum(arr) # This code is contributed by shinjanpatra
C#
// C# program for the above approach
using System;
public class GFG {
// Function to calculate sum of
// maximum of all subarrays
public static void findSum(int []a) {
int ans = 0;
int prev = -1;
// Iterate over the range [30, 0]
for (int i = 30; i >= 0; i--) {
int mask = (1 << i);
// Inner loop through the
// length of the array
for (int j = 0; j < a.Length; j++) {
// Divide the array such
// that no subarray will
// have any index set to -1
if (a[j] == -1) {
ans += findSumOfValuesOfRange(a, prev + 1, j - 1, mask);
prev = j;
}
}
// Find the sum of subarray
ans += findSumOfValuesOfRange(a, prev + 1, a.Length - 1, mask);
}
// Print the sum obtained
Console.WriteLine(ans);
}
// Function that takes any subarray
// S and return values contributed
// by only the subarrays in S containing mask
public static int findSumOfValuesOfRange(int[] a, int low,
int high, int mask)
{
if (low > high)
return 0;
// Stores count even, odd count of
// occurrences and maximum element
int evenCount = 0, oddCount = 0, countLargestNumber = 0;
int prev = low - 1, ans = 0;
// Traverse from low to high
for (int i = low; i <= high; i++) {
// Checking if this position
// in the array is mask
if ((mask & a[i]) > 0) {
// Mask is the largest
// number in subarray.
// Increment count by 1
countLargestNumber++;
// Store parity as 0 or 1
int parity = countLargestNumber % 2;
// Setting a[i]=-1, this
// will help in splitting
// array into subarrays
a[i] = -1;
int count = i - prev;
ans += count;
// Add values contributed
// by those subarrays that
// have an odd frequency
ans += (count - 1) * ((parity == 1) ? evenCount : oddCount);
ans += ((parity == 1) ? oddCount : evenCount);
// Adding values contributed
// by those subarrays that
// have an even frequency
ans += 2 * (count - 1) * ((parity == 1) ? oddCount : evenCount);
ans += 2 * ((parity == 1) ? evenCount : oddCount);
// Set the prev pointer
// to this position
prev = i;
if (parity == 1)
oddCount += count;
else
evenCount += count;
}
}
if (prev != low - 1) {
int count = high - prev;
int parity = countLargestNumber % 2;
ans += count * ((parity == 1) ? oddCount : evenCount);
ans += 2 * count * ((parity == 1) ? evenCount : oddCount);
ans *= mask;
}
// Return the readonly sum
return ans;
}
// Driver Code
public static void Main(String[] args) {
int[] arr = { 2, 1, 4, 4, 2 };
// Function call
findSum(arr);
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program for the above approach
// Function to calculate sum of
// maximum of all subarrays
function findSum(a) {
var ans = 0;
var prev = -1;
// Iterate over the range [30, 0]
for (var i = 30; i >= 0; i--) {
var mask = (1 << i);
// Inner loop through the
// length of the array
for (var j = 0; j < a.length; j++) {
// Divide the array such
// that no subarray will
// have any index set to -1
if (a[j] == -1) {
ans += findSumOfValuesOfRange(a, prev + 1, j - 1, mask);
prev = j;
}
}
// Find the sum of subarray
ans += findSumOfValuesOfRange(a, prev + 1, a.length - 1, mask);
}
// Print the sum obtained
document.write(ans);
}
// Function that takes any subarray
// S and return values contributed
// by only the subarrays in S containing mask
function findSumOfValuesOfRange(a , low , high , mask) {
if (low > high)
return 0;
// Stores count even, odd count of
// occurrences and maximum element
var evenCount = 0, oddCount = 0, countLargestNumber = 0;
var prev = low - 1, ans = 0;
// Traverse from low to high
for (var i = low; i <= high; i++) {
// Checking if this position
// in the array is mask
if ((mask & a[i]) > 0) {
// Mask is the largest
// number in subarray.
// Increment count by 1
countLargestNumber++;
// Store parity as 0 or 1
var parity = countLargestNumber % 2;
// Setting a[i]=-1, this
// will help in splitting
// array into subarrays
a[i] = -1;
var count = i - prev;
ans += count;
// Add values contributed
// by those subarrays that
// have an odd frequency
ans += (count - 1) * ((parity == 1) ? evenCount : oddCount);
ans += ((parity == 1) ? oddCount : evenCount);
// Adding values contributed
// by those subarrays that
// have an even frequency
ans += 2 * (count - 1) * ((parity == 1) ? oddCount : evenCount);
ans += 2 * ((parity == 1) ? evenCount : oddCount);
// Set the prev pointer
// to this position
prev = i;
if (parity == 1)
oddCount += count;
else
evenCount += count;
}
}
if (prev != low - 1) {
var count = high - prev;
var parity = countLargestNumber % 2;
ans += count * ((parity == 1) ? oddCount : evenCount);
ans += 2 * count * ((parity == 1) ? evenCount : oddCount);
ans *= mask;
}
// Return the final sum
return ans;
}
// Driver Code
var arr = [ 2, 1, 4, 4, 2 ];
// Function call
findSum(arr);
// This code is contributed by gauravrajput1
</script>
Producción:
75
Complejidad temporal: O(30*N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array