Let Al1n] be an array of integers, where n2 1. Write an algorithm using pseudoco

Question

Let Al1n] be an array of integers, where n2 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 = , then the subarray has sum 0, so the algorithms returns the indexes of the subarray which are 3, 5. if A = , then the algorithm prints "no subarray with sum 0". .

Explanation / Answer

input : A array of integer of size n

output: i,j two indice represetnting the subarray

procedure

there are two for loops

one with i goes from 1 to N

and second with j goes from i to N

thus number inner loop run N-i times for each outer loop

complexity = N + N-1 +N-2+ .......+ 1

= n(n+1)/2 = O(n2)

For i = 1 to n do

subarray_sum = 0

         For j = i to n do

         Subarray_sum = Subarray_sum + A[j]

         IF sum is equal to 0

       Return i,j

        End IF

        End For

End For

Print “no indices found”

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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