Let A[1..n] be an array of integers, where n 1. Write an algorithm using pseudoc

ID: 3591150 • Letter: L

Question

Let A[1..n] be an array of integers, where n 1. Write an algorithm using pseudocode that finds whether A contains a subarray with sum 0. If yes, then return the indexes of the subarray. If no, then print a message. What is the Running Time of your algorithm?

Note: If A has multiple subarrays with sum 0, then just return one of them.

Here are some examples:

*if A = <5, 3, -2, 5, -3, 8>, then the subarray <-2, 5, -3> has sum 0, so the algorithms returns the indexes of the subarray which are 3, 5.

*if A = <2, 10, 6, -2, 3, -8>, then the algorithm prints "no subarray with sum 0".

Explanation / Answer

Simple solution

Check all subarray and their sum

Algo:

for i = 1 to n
cur_sum = 0
for j = i+1 to n
if (cur_sum == 0 ) return (i, j-1)
cur_sum = cur_sum + A[j]

This algorithm runs in O(n^2)

Navigate

Let A[1..n] be an array of distinct positive integers, and let t be a positive i

Let A[1..n] be an array of n distinct numbers, (i, j) is called an inversion of

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

Let A[1..n] be an array of integers, where n 1. Write an algorithm using pseudoc

Question

Explanation / Answer

Related Questions

Navigate