CODEWITHSUNDEEP
javapythonarraysalgorithmtime-complexity
Remus Case
Remus Case

Reputation: 470

How can I find sum of subarray of size k with every possibilities in the array?

I have done this with consecutive subarray but to find sum of subarray of size k and of every possibility is difficult and I have been facing dead ends. Please help me out here.

        for(int i=0;i<n;i++)
            {
                a[i] = sc.nextInt();
            }
            Arrays.sort(a);
            for(int j=0;j<k;j++)
            {
                sum = sum + a[j];
            }
        }
        System.out.println(sum);

This is something I am trying to do get minimum sum but I don't know how can I get subarray of size k.

Now I want to count how many times the subarray size sum repeats in the array.

For Example : Given array [2, 5, 9, 7, 6, 3] and subarray of length k = 3; Than we have to find check for every possibility sum in the array like [2, 5, 9] = 16; [2, 9, 7] = 18; [5, 6, 3] = 14...Same goes to each number checking for each subsequence of subarray of size k.

Upvotes: 2

Views: 1470

Answers (3)

Ida Taki
Ida Taki

Reputation: 1

Most of the time, problems like "obtain all the non-contiguous subsequences of length K in an array" or "split an array into K subarray" have an extra condition which you should consider it to find an approach. here your approach is to sort the array in increasing order and calculate the sum of the first K element.

sm = 0
k = 3
arr = [2, 5, 9, 7, 6, 3]
arr.sort()
for i in range(k):
    sm += arr[i]
print(sm)

Upvotes: 0

Dipen Dadhaniya
Dipen Dadhaniya

Reputation: 4630

We can do this:

from itertools import combinations
from heapq import nsmallest
from math import factorial


arr = [2, 3, 2, 1, 1, 1, 1, 1, 2]
k = 3


def optimal(arr, k):
    if len(arr) < k:
        return 0

    k_smallest_elements = nsmallest(k, arr) # n * log(k)

    needed_count = k_smallest_elements.count(k_smallest_elements[k - 1]) 
    actual_count = arr.count(k_smallest_elements[k - 1])

    # Return actual_count Choose needed_count.
    return factorial(actual_count) // factorial(needed_count) // factorial(actual_count - needed_count)


def sub_optimal(arr, k):
    if len(arr) < k:
        return 0

    arr = sorted(arr) # n * log(n)
    needed_count = arr[:k].count(arr[k - 1])
    actual_count = arr.count(arr[k - 1])

    # Return actual_count Choose needed_count.
    return factorial(actual_count) // factorial(needed_count) // factorial(actual_count - needed_count)


def brute_force(arr, k):
    min_sum = sum(sorted(arr)[:k])
    return len([k_len_subset for k_len_subset in combinations(arr, k) if sum(k_len_subset) == min_sum])


count = optimal(arr, k)
assert count == sub_optimal(arr, k) == brute_force(arr, k) # Remove this line in production.
print(count)

Upvotes: 0

Eric J.
Eric J.

Reputation: 150108

In general there are two variants of this problem. I'll present solutions to both to help future readers. You're looking for the smallest sum (others may want largest sum) for an arbitrary subarray (pick any K elements). Another common, similar problem is to find the smallest or largest sum for a contiguous subarray of either given (pick k adjacent elements) or arbitrary length.

Arbitrary Subarray

You can solve this in O(n Log n) time. Sort the subarray then sum the last k elements in the sorted array.

By sorting, the largest elements are at the end of the sorted array. You get the largest sum by summing the largest elements.

That is what your code appears to do.

Contiguous Subarray

K adjacent elements

You can solve this in O(n) time by computing the sum of a sliding window across your array. The first window consists of the elements at index 0..(k-1) and the last of elements (n-2)..n.

Compute the sum for the first window.

For each additional window:

  • The sum of that window is the sum of the previous window, subtracting the element that just fell out (array element just below the start of the window), and adding the element that was just included (array element that just became included in the current window).
  • Take the min or max (as needed) of the current window sum and the highest sum recorded so far. That's your current lowest or highest sum.

After processing the last window, your min or max variable represents the lowest or highest sum (as appropriate). If needed, you can also record the starting index of that window whenever max changes.

Arbitrary number of adjacent elements

Interestingly, the highest sum for a subarray of arbitrary length can also be calculated in O(n) time using a clever approach known as Kadane's algorithm.

Upvotes: 2

Related Questions