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>
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>
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>
75
Complejidad temporal: O(30*N)
Espacio auxiliar: O(1)
Tema relacionado: Subarrays, subsecuencias y subconjuntos en array