Given an array arr[] of N integers, the task is to find the minimum value of K such that the sum of elements on indices that are multiples of K is the maximum possible.
Example:
Input: arr[] = {-3, 4}
Output: 2
Explanation: For the given array, it the value of K = 1, then the multiples of K are {1, 2} which sums up to arr[1] + arr[2] = -3 + 4 = 1. For K = 2, the valid multiple of K is 2 and hence the sum is arr[2] = 4, which is the maximum possible. Hence, K = 2 is a valid answer.Input: arr[] = {-1, -2, -3}
Output: 2
Approach: The given problem can be solved by a similar to that of the Sieve of Eratosthenes. The idea is to calculate the sum for all possible values of K in the range [1, N] by iterating over each multiple of K as done while marking the non-prime elements in the Sieve. The value of K giving the maximum sum is the required answer.
Below is the implementation of the above approach:
C++
// C++ Program of the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum K such that// the sum of elements on indices that// are multiples of K is maximum possibleint maxSum(int arr[], int N){ // Stores the maximum sum and // respective K value int maxSum = INT_MIN, ans = -1; // Loop to iterate over all // value of K in range [1, N] for (int K = 1; K <= N; K++) { int sum = 0; // Iterating over all // multiples of K for (int i = K; i <= N; i += K) { sum += arr[i - 1]; } // Update Maximum Sum if (sum > maxSum) { maxSum = sum; ans = K; } } // Return Answer return ans;}// Driver Codeint main(){ int arr[] = { -1, -2, -3 }; int N = sizeof(arr) / sizeof(int); cout << maxSum(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ // Function to find minimum K such that// the sum of elements on indices that// are multiples of K is maximum possiblestatic int maxSum(int arr[], int N){ // Stores the maximum sum and // respective K value int maxSum = Integer.MIN_VALUE, ans = -1; // Loop to iterate over all // value of K in range [1, N] for(int K = 1; K <= N; K++) { int sum = 0; // Iterating over all // multiples of K for(int i = K; i <= N; i += K) { sum += arr[i - 1]; } // Update Maximum Sum if (sum > maxSum) { maxSum = sum; ans = K; } } // Return Answer return ans;}// Driver Codepublic static void main(String args[]){ int arr[] = { -1, -2, -3 }; int N = arr.length; System.out.println(maxSum(arr, N));}}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python program for the above approachimport sys# Function to find minimum K such that# the sum of elements on indices that# are multiples of K is maximum possibledef maxSum(arr, N): # Stores the maximum sum and # respective K value maxSum = -sys.maxsize; ans = -1; # Loop to iterate over all # value of K in range [1, N] for K in range(1,N+1): sum = 0; # Iterating over all # multiples of K for i in range(K, N + 1,K): sum += arr[i - 1]; # Update Maximum Sum if (sum > maxSum): maxSum = sum; ans = K; # Return Answer return ans;# Driver Codeif __name__ == '__main__': arr = [ -1, -2, -3 ]; N = len(arr); print(maxSum(arr, N));# This code is contributed by gauravrajput1 |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find minimum K such that // the sum of elements on indices that // are multiples of K is maximum possible static int maxSum(int []arr, int N) { // Stores the maximum sum and // respective K value int maxSum = int.MinValue, ans = -1; // Loop to iterate over all // value of K in range [1, N] for(int K = 1; K <= N; K++) { int sum = 0; // Iterating over all // multiples of K for(int i = K; i <= N; i += K) { sum += arr[i - 1]; } // Update Maximum Sum if (sum > maxSum) { maxSum = sum; ans = K; } } // Return Answer return ans; } // Driver Code public static void Main(String []args) { int []arr = { -1, -2, -3 }; int N = arr.Length; Console.WriteLine(maxSum(arr, N)); }}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript code for the above approach // Function to find minimum K such that // the sum of elements on indices that // are multiples of K is maximum possible function maxSum(arr, N) { // Stores the maximum sum and // respective K value let maxSum = -999999; let ans = -1; // Loop to iterate over all // value of K in range [1, N] for (let K = 1; K <= N; K++) { let sum = 0; // Iterating over all // multiples of K for (let i = K; i <= N; i += K) { sum = sum + arr[i - 1]; } // Update Maximum Sum if (sum > maxSum) { maxSum = sum; ans = K; } } // Return Answer return ans; } // Driver Code let arr = [-1, -2, -3]; let N = arr.length; document.write(maxSum(arr, N));// This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N*log N)
Auxiliary space: O(1)
Another Approach:
- First, we calculate the prefix sum of the given array. Let’s say prefixSum[i] stores the sum of the first i elements of the array.
- Then, we iterate over all possible values of K in the range [1, N] and calculate the sum of elements on indices that are multiples of K. This can be done in constant time by using prefixSum array. Let’s say this sum is sumK.
- We update the maximum sum and the corresponding value of K whenever we find a new maximum sum.
- Finally, we return the value of K that gave us the maximum sum.
Below is the implementation of the above approach:
C++
#include <iostream>#include <vector>using namespace std;int maxSum(vector<int>& arr) { int n = arr.size(); vector<int> prefixSum(n+1, 0); // prefixSum[i] stores sum of first i elements of arr for(int i=1; i<=n; i++) { prefixSum[i] = prefixSum[i-1] + arr[i-1]; } int maxSum = -999999999, ans = -1; for(int K=1; K<=n; K++) { int sumK = 0; for(int i=K; i<=n; i+=K) { sumK += prefixSum[i] - prefixSum[i-K]; } if(sumK > maxSum) { maxSum = sumK; ans = K; } } return ans;}int main() { vector<int> arr = {-1, -2, -3}; cout << maxSum(arr) << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class MaxSumFinder { // Function to find K with the maximum sum public static int maxSum(List<Integer> arr) { int n = arr.size(); List<Integer> prefixSum = new ArrayList<>(n + 1); // Initialize prefixSum with 0 and calculate the prefix sum for (int i = 0; i <= n; i++) { prefixSum.add(0); } for (int i = 1; i <= n; i++) { prefixSum.set(i, prefixSum.get(i - 1) + arr.get(i - 1)); } int maxSum = Integer.MIN_VALUE; // Initialize maxSum to a small value int ans = -1; // Initialize ans to -1, indicating no valid K found yet // Loop through different values of K for (int K = 1; K <= n; K++) { int sumK = 0; // Calculate the sum of subarrays of size K for (int i = K; i <= n; i += K) { sumK += prefixSum.get(i) - prefixSum.get(i - K); } // If the sum for this K is greater than the maxSum, update maxSum and ans if (sumK > maxSum) { maxSum = sumK; ans = K; } } return ans; // Return the K with the maximum sum } public static void main(String[] args) { List<Integer> arr = List.of(-1, -2, -3); System.out.println(maxSum(arr)); }} |
Python3
def maxSum(arr): n = len(arr) prefixSum = [0] * (n + 1) # Initialize a list to store prefix sums, initialized with zeros # Calculate prefix sums for the input array for i in range(1, n + 1): prefixSum[i] = prefixSum[i - 1] + arr[i - 1] maxSum = -999999999 # Initialize a variable to store the maximum sum found so far ans = -1 # Initialize a variable to store the value of K that results in the maximum sum # Loop through possible values of K for K in range(1, n + 1): sumK = 0 # Calculate the sum of elements at intervals of K for i in range(K, n + 1, K): sumK += prefixSum[i] - prefixSum[i - K] # Update maxSum and ans if a higher sum is found if sumK > maxSum: maxSum = sumK ans = K return ans# Driver Codeif __name__ == "__main__": arr = [-1, -2, -3] result = maxSum(arr) print( result) |
C#
using System;using System.Collections.Generic;class Program{ // Function to find the value of K that maximizes the sum of subarrays static int MaxSum(List<int> arr) { int n = arr.Count; List<int> prefixSum = new List<int>(n + 1); // Initialize prefixSum with zeros for (int i = 0; i <= n; i++) { prefixSum.Add(0); } // Calculate the prefix sum of the array for (int i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i - 1]; } int maxSum = int.MinValue; int ans = -1; // Iterate through possible values of K for (int K = 1; K <= n; K++) { int sumK = 0; // Calculate the sum of subarrays of length K for (int i = K; i <= n; i += K) { sumK += prefixSum[i] - prefixSum[i - K]; } // Update the maximum sum and the corresponding value of K if (sumK > maxSum) { maxSum = sumK; ans = K; } } return ans; } static void Main() { List<int> arr = new List<int> { -1, -2, -3 }; // Find the value of K that maximizes the sum and print it Console.WriteLine(MaxSum(arr)); }} |
Javascript
function maxSum(arr) { const n = arr.length; const prefixSum = new Array(n + 1).fill(0); // Calculate the prefix sum for (let i = 1; i <= n; i++) { prefixSum[i] = prefixSum[i - 1] + arr[i - 1]; } let maxSum = Number.MIN_SAFE_INTEGER; // Initialize maxSum to a small value let ans = -1; // Initialize ans to -1, indicating no valid K found yet // Iterate over all possible values of K for (let K = 1; K <= n; K++) { let sumK = 0; // Calculate the sum of subarrays directly for (let i = 0; i < n; i++) { if ((i + 1) % K === 0) { sumK += arr[i]; } } // Update maxSum and ans if the sum for this K is greater than the current maxSum if (sumK > maxSum) { maxSum = sumK; ans = K; } } return ans; // Return the K with the maximum sum}// Example usageconst arr = [-1, -2, -3];console.log(maxSum(arr)); // Output the result of maxSum function for the given array |
Output
2
Time Complexity: O(n*logn)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
