Let\'s define two functions(or methods in Java) prefixSum and suffixSum for an i
ID: 3870975 • Letter: L
Question
Let's define two functions(or methods in Java) prefixSum and suffixSum for an integer array of size n, Assume that the array indices starts with index 1 ( java has 0 based index)
-Function prefixSum(i) denotes the sum of first i numbers of the array
-Function suffixSum(i) denotes the sum of last n-i+1 numbers of the array
In this optimization problem, write pseudo code to find the minimum index i for which prefixSum(i) +suffixSum(i) become minimum
Hint you should pass A as a parameter and return the minimum index i.
Explanation / Answer
Function prefixSum(A[1, ... , n], i)
{
// initialize sum to 0
sum = 0
// find the sum of first i elements
for j <- 1 to i
{
sum = sum + A[i]
}
return sum
}
Function suffixSum(A[1, ... , n], i)
{
n = A.length
// initialize sum to 0
sum = 0
// find the sum of last n-i+1 elements
for j <- n down to i-1
{
sum = sum + A[i]
}
return sum
}
Function minIndex(A)
{
n = A.length
index = 1
sum = Infinite value
for i <- 1 to n
{
// get the sum of prefix and suffix
temp = prefixSum(A, i) + suffixSum(A, i)
// if the sum at this index is less than
// previous sums
if(temp < sum)
{
// update index
index = i
// update sum
sum = temp
}
}
return index
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.