Find index with minimum sum of prefix and suffix sums in an array
Here given code implementation process.
/*
C program for
Find index with minimum sum of prefix and
suffix sums in an Array
*/
#include <stdio.h>
void minPrefixSuffix(int arr[], int n)
{
// This is use collect prefix sum
int prefix[n];
// This is use collect suffix sum
int suffix[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
printf(" Position : %d", position);
}
int main(int argc, char
const *argv[])
{
int arr[] = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
minPrefixSuffix(arr, n);
return 0;
}Output
Position : 4/*
Java program for
Find index with minimum sum of prefix and suffix sums in an array
*/
public class PrefixSuffix
{
public void minPrefixSuffix(int[] arr, int n)
{
// This is use collect prefix sum
int[] prefix = new int[n];
// This is use collect suffix sum
int[] suffix = new int[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
System.out.print(" Position : " + position);
}
public static void main(String[] args)
{
PrefixSuffix task = new PrefixSuffix();
int[] arr = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = arr.length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task.minPrefixSuffix(arr, n);
}
}Output
Position : 4// Include header file
#include <iostream>
using namespace std;
/*
C++ program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
public: void minPrefixSuffix(int arr[], int n)
{
// This is use collect prefix sum
int prefix[n];
// This is use collect suffix sum
int suffix[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
cout << " Position : " << position;
}
};
int main()
{
PrefixSuffix *task = new PrefixSuffix();
int arr[] = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = sizeof(arr) / sizeof(arr[0]);
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task->minPrefixSuffix(arr, n);
return 0;
}Output
Position : 4// Include namespace system
using System;
/*
Csharp program for
Find index with minimum sum of prefix and
suffix sums in an Array
*/
public class PrefixSuffix
{
public void minPrefixSuffix(int[] arr, int n)
{
// This is use collect prefix sum
int[] prefix = new int[n];
// This is use collect suffix sum
int[] suffix = new int[n];
int position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (int i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (int i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
int sum = prefix[0] + suffix[0];
for (int i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
Console.Write(" Position : " + position);
}
public static void Main(String[] args)
{
PrefixSuffix task = new PrefixSuffix();
int[] arr = {
3 , -6 , 1 , 6 , -7 , -4 , -3 , -2 , -1 , 6
};
int n = arr.Length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task.minPrefixSuffix(arr, n);
}
}Output
Position : 4package main
import "fmt"
/*
Go program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
func minPrefixSuffix(arr[] int, n int) {
// This is use collect prefix sum
var prefix = make([] int, n)
// This is use collect suffix sum
var suffix = make([] int, n)
var position int = 0
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
// Calculate prefix sum
for i := 1 ; i < n ; i++ {
prefix[i] = prefix[i - 1] + arr[i]
}
// Calculate suffix sum
for i := n - 2 ; i >= 0 ; i-- {
suffix[i] = suffix[i + 1] + arr[i]
}
// First pair of prefix and suffix
var sum int = prefix[0] + suffix[0]
for i := 1 ; i < n ; i++ {
if prefix[i] + suffix[i] < sum {
position = i
// We get new pair
sum = prefix[i] + suffix[i]
}
}
// Display calculated position
fmt.Print(" Position : ", position)
}
func main() {
var arr = [] int {3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 }
var n int = len(arr)
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
minPrefixSuffix(arr, n)
}Output
Position : 4<?php
/*
Php program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
public function minPrefixSuffix($arr, $n)
{
// This is use collect prefix sum
$prefix = array_fill(0, $n, 0);
// This is use collect suffix sum
$suffix = array_fill(0, $n, 0);
$position = 0;
$prefix[0] = $arr[0];
$suffix[$n - 1] = $arr[$n - 1];
// Calculate prefix sum
for ($i = 1; $i < $n; ++$i)
{
$prefix[$i] = $prefix[$i - 1] + $arr[$i];
}
// Calculate suffix sum
for ($i = $n - 2; $i >= 0; --$i)
{
$suffix[$i] = $suffix[$i + 1] + $arr[$i];
}
// First pair of prefix and suffix
$sum = $prefix[0] + $suffix[0];
for ($i = 1; $i < $n; ++$i)
{
if ($prefix[$i] + $suffix[$i] < $sum)
{
$position = $i;
// We get new pair
$sum = $prefix[$i] + $suffix[$i];
}
}
// Display calculated position
echo(" Position : ".$position);
}
}
function main()
{
$task = new PrefixSuffix();
$arr = array(3, -6, 1, 6, -7, -4, -3, -2, -1, 6);
$n = count($arr);
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
$task->minPrefixSuffix($arr, $n);
}
main();Output
Position : 4/*
Node JS program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
minPrefixSuffix(arr, n)
{
// This is use collect prefix sum
var prefix = Array(n).fill(0);
// This is use collect suffix sum
var suffix = Array(n).fill(0);
var position = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
// Calculate prefix sum
for (var i = 1; i < n; ++i)
{
prefix[i] = prefix[i - 1] + arr[i];
}
// Calculate suffix sum
for (var i = n - 2; i >= 0; --i)
{
suffix[i] = suffix[i + 1] + arr[i];
}
// First pair of prefix and suffix
var sum = prefix[0] + suffix[0];
for (var i = 1; i < n; ++i)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
}
// Display calculated position
process.stdout.write(" Position : " + position);
}
}
function main()
{
var task = new PrefixSuffix();
var arr = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6];
var n = arr.length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task.minPrefixSuffix(arr, n);
}
main();Output
Position : 4# Python 3 program for
# Find index with minimum sum of prefix and suffix sums in an Array
class PrefixSuffix :
def minPrefixSuffix(self, arr, n) :
# This is use collect prefix sum
prefix = [0] * (n)
# This is use collect suffix sum
suffix = [0] * (n)
position = 0
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
i = 1
# Calculate prefix sum
while (i < n) :
prefix[i] = prefix[i - 1] + arr[i]
i += 1
i = n - 2
# Calculate suffix sum
while (i >= 0) :
suffix[i] = suffix[i + 1] + arr[i]
i -= 1
# First pair of prefix and suffix
sum = prefix[0] + suffix[0]
i = 1
while (i < n) :
if (prefix[i] + suffix[i] < sum) :
position = i
# We get new pair
sum = prefix[i] + suffix[i]
i += 1
# Display calculated position
print(" Position : ", position, end = "")
def main() :
task = PrefixSuffix()
arr = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6]
n = len(arr)
# arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
# -----------------------------------------------
# position 0 1 2 3 4 5 6 7 8 9
# Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
# Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
# -----------------------------------------------
# position 4 contain minimum prefix and suffix
# arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
# ↑
# position
task.minPrefixSuffix(arr, n)
if __name__ == "__main__": main()Output
Position : 4# Ruby program for
# Find index with minimum sum of prefix and suffix sums in an Array
class PrefixSuffix
def minPrefixSuffix(arr, n)
# This is use collect prefix sum
prefix = Array.new(n) {0}
# This is use collect suffix sum
suffix = Array.new(n) {0}
position = 0
prefix[0] = arr[0]
suffix[n - 1] = arr[n - 1]
i = 1
# Calculate prefix sum
while (i < n)
prefix[i] = prefix[i - 1] + arr[i]
i += 1
end
i = n - 2
# Calculate suffix sum
while (i >= 0)
suffix[i] = suffix[i + 1] + arr[i]
i -= 1
end
# First pair of prefix and suffix
sum = prefix[0] + suffix[0]
i = 1
while (i < n)
if (prefix[i] + suffix[i] < sum)
position = i
# We get new pair
sum = prefix[i] + suffix[i]
end
i += 1
end
# Display calculated position
print(" Position : ", position)
end
end
def main()
task = PrefixSuffix.new()
arr = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6]
n = arr.length
# arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
# -----------------------------------------------
# position 0 1 2 3 4 5 6 7 8 9
# Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
# Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
# -----------------------------------------------
# position 4 contain minimum prefix and suffix
# arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
# ↑
# position
task.minPrefixSuffix(arr, n)
end
main()Output
Position : 4/*
Scala program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix()
{
def minPrefixSuffix(arr: Array[Int], n: Int): Unit = {
// This is use collect prefix sum
var prefix: Array[Int] = Array.fill[Int](n)(0);
// This is use collect suffix sum
var suffix: Array[Int] = Array.fill[Int](n)(0);
var position: Int = 0;
prefix(0) = arr(0);
suffix(n - 1) = arr(n - 1);
var i: Int = 1;
// Calculate prefix sum
while (i < n)
{
prefix(i) = prefix(i - 1) + arr(i);
i += 1;
}
i = n - 2;
// Calculate suffix sum
while (i >= 0)
{
suffix(i) = suffix(i + 1) + arr(i);
i -= 1;
}
// First pair of prefix and suffix
var sum: Int = prefix(0) + suffix(0);
i = 1;
while (i < n)
{
if (prefix(i) + suffix(i) < sum)
{
position = i;
// We get new pair
sum = prefix(i) + suffix(i);
}
i += 1;
}
// Display calculated position
print(" Position : " + position);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: PrefixSuffix = new PrefixSuffix();
var arr: Array[Int] = Array(3, -6, 1, 6, -7, -4, -3, -2, -1, 6);
var n: Int = arr.length;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task.minPrefixSuffix(arr, n);
}
}Output
Position : 4import Foundation;
/*
Swift 4 program for
Find index with minimum sum of prefix and suffix sums in an Array
*/
class PrefixSuffix
{
func minPrefixSuffix(_ arr: [Int], _ n: Int)
{
// This is use collect prefix sum
var prefix: [Int] = Array(repeating: 0, count: n);
// This is use collect suffix sum
var suffix: [Int] = Array(repeating: 0, count: n);
var position: Int = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
var i: Int = 1;
// Calculate prefix sum
while (i < n)
{
prefix[i] = prefix[i - 1] + arr[i];
i += 1;
}
i = n - 2;
// Calculate suffix sum
while (i >= 0)
{
suffix[i] = suffix[i + 1] + arr[i];
i -= 1;
}
// First pair of prefix and suffix
var sum: Int = prefix[0] + suffix[0];
i = 1;
while (i < n)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
i += 1;
}
// Display calculated position
print(" Position : ", position, terminator: "");
}
}
func main()
{
let task: PrefixSuffix = PrefixSuffix();
let arr: [Int] = [3, -6, 1, 6, -7, -4, -3, -2, -1, 6];
let n: Int = arr.count;
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task.minPrefixSuffix(arr, n);
}
main();Output
Position : 4/*
Kotlin program for
Find index with minimum sum of prefix and
suffix sums in an array
*/
class PrefixSuffix
{
fun minPrefixSuffix(arr: Array < Int > , n: Int): Unit
{
// This is use collect prefix sum
var prefix: Array < Int > = Array(n)
{
0
};
// This is use collect suffix sum
var suffix: Array < Int > = Array(n)
{
0
};
var position: Int = 0;
prefix[0] = arr[0];
suffix[n - 1] = arr[n - 1];
var i: Int = 1;
// Calculate prefix sum
while (i < n)
{
prefix[i] = prefix[i - 1] + arr[i];
i += 1;
}
i = n - 2;
// Calculate suffix sum
while (i >= 0)
{
suffix[i] = suffix[i + 1] + arr[i];
i -= 1;
}
// First pair of prefix and suffix
var sum: Int = prefix[0] + suffix[0];
i = 1;
while (i < n)
{
if (prefix[i] + suffix[i] < sum)
{
position = i;
// We get new pair
sum = prefix[i] + suffix[i];
}
i += 1;
}
// Display calculated position
print(" Position : " + position);
}
}
fun main(args: Array < String > ): Unit
{
val task: PrefixSuffix = PrefixSuffix();
val arr: Array < Int > = arrayOf(3, -6, 1, 6, -7, -4, -3, -2, -1, 6);
val n: Int = arr.count();
/*
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
-----------------------------------------------
position 0 1 2 3 4 5 6 7 8 9
Prefix sum [3 -3 -2 4 -3 -7 -10 -12 -13 -7]
Suffix sum [-7 -10 -4 -5 -11 -4 0 3 5 6]
-----------------------------------------------
position 4 contain minimum prefix and suffix
arr [3, -6, 1, 6, -7, -4, -3, -2, -1 , 6 ]
↑
position
*/
task.minPrefixSuffix(arr, n);
}Output
Position : 4
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment