Skip to main content

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 : 4
package 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 : 4
import 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




Comment

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