CODEWITHSUNDEEP
arraysalgorithmdynamic-programming
Herp Derp
Herp Derp

Reputation: 85

Consecutve Subset Array Sum is a certain integer algorithm

Here is the problem:

Given is an array A of n integers, a seperate integer M, and an integer d. Find a consecutive subarray S of A, such that the size of the subarray is less than or equal to d and the sum of all the elements in S is M. Return the indexes of A that make the left and right index the subarray S. All numbers are positive.

If there is more than one result, give the rightmost result.

We have to make the algorithm run in better time than: O(n^2) or O(n*d). So basically it has to be O(nlog(n)), and divide and conquer I'm assuming is the way to go. I know how to do maximum continuous subarray problem, but that is made easier because when you divide and conquer you can look for max subarrays, with this one you don't really know what you are looking for in the subarrays, if that makes sense, since the solution could come from combinations of subarrays with small numbers and subarrays with big

Any help to lead me to the solution would be greatly appreciated!

I'm about 80% sure at this point that this is not possible... I keep looking it over and I can not think of a single way to make this work, is it possible this is a massive trick question?

Upvotes: 1

Views: 200

Answers (3)

n. m. could be an AI
n. m. could be an AI

Reputation: 119847

If all numbers are non-negative, this has a straightforward O(N) solution. The requirement of length<=d doesn't add any complexity, just add a check current_length<=d. I assume there are negative numbers in the array. We need additional O(N) space.

  1. Compute prefix-sum of each index of S: p(i) = sum(S,0,i). Place p(i) in an additional array P: P[i]=p(i).
  2. Make a copy of P: PSorted = P. Sort PSorted with a stable sort algorithm. We use it as a map prefix-sum -> index, with the index being a tie-breaker.
  3. For each index k of S, starting from the largest:
    • Set p = P[k].
    • Look up p-M in PSorted using binary search, biased to the right. Say the resulting index is q.
    • If found, and q-k<d, return the answer (k,q).

This has overall O(n log n) complexity.

Expected running time can be reduced to O(N) if one uses a hash table instead of a sorted array, but one needs to be careful to always return the rightmost index which is smaller than the current index.

Upvotes: 0

Arun Tyagi
Arun Tyagi

Reputation: 2256

Correctly working algorithm, time complexity is O(n), if you count number operations closely.

 public void SubArraySum(int[] arr, int d, int sum)
        {
            int n = arr.Length-1;
            int curr_sum = arr[0], start = 0, i;
            /* Add elements one by one to curr_sum and if the curr_sum exceeds the
               sum, then remove starting element */
            for (i = 1; i <= n; i++)
            {
                // If curr_sum exceeds the sum, then remove the starting elements
                while (curr_sum > sum && start < i - 1)
                {
                    curr_sum = curr_sum - arr[start];
                    start++;
                }

                // If curr_sum becomes equal to sum, then return true
                if (curr_sum == sum && Math.Abs(start - i - 1) <= d)
                {
                    Console.WriteLine("Sum found between indexes {0} and {1}", start, i - 1);
return;
                }

                // Add this element to curr_sum
                if (i < n)
                    curr_sum = curr_sum + arr[i];
            }

            // If we reach here, then no subarray
            Console.WriteLine("No subarray found");
        }

Hope this help :)

Upvotes: 0

mcdowella
mcdowella

Reputation: 19601

This is relatively easy if the integers in A are >= 0, because you can just maintain a couple of pointers that define an interval with sum close to M and slide this along the array from right to left. Is it possible that you have missed some extra information like this in the question?

OK - here is some expansion. You have a left pointer and a right pointer. Move the right hand pointer from right to left, maintaining the invariant that the left hand pointer is no more than d places from the right hand pointer, and the sum of elements enclosed by the two pointers is the greatest possible number <= M. Repeatedly move the right hand pointer one step to the left and move the left hand pointer to the left until either you reach the limit of d or moving it further would produce a sum > M. Each time you move a pointer you can increment or decrement to maintain a running total of the sum enclosed by the two pointers.

Because the numbers are >= 0 every time you move the right hand pointer you decrease the sum or it stays the same so you always want to leave the left hand pointer the same or move it to the left. Because the numbers are >=0 you know that if there is an answer starting at the right hand pointer position you will find it with the left hand pointer position - anything that doesn't extend as far as the left hand pointer is too small, and anything that extends further is too large, except in the case where there are zeros and in that case you will find a solution, it's just that there are other solutions.

Each pointer is moved only in one direction so the maximum number of pointer movements is O(n) and the cost per pointer move is fixed so the complexity is O(n)

Upvotes: 1

Related Questions