Little Chef and Sums Codechef Solution

Hello Programmers In this post, you will know how to solve the Little Chef and Sums Codechef Solution.

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

Our little chef is fond of doing additions/sums in his free time. Today, he has an array A consisting of N positive integers and he will compute prefix and suffix sums over this array.

He first defines two functions prefixSum(i) and suffixSum(i) for the array as follows. The function prefixSum(i) denotes the sum of first i numbers of the array. Similarly, he defines suffixSum(i) as the sum of last N – i + 1 numbers of the array.

Little Chef is interested in finding the minimum index i for which the value prefixSum(i) + suffixSum(i) is the minimum. In other words, first you should minimize the value of prefixSum(i) + suffixSum(i), and then find the least index i for which this value is attained.

Since, he is very busy preparing the dishes for the guests, can you help him solve this problem?

Input

The first line of the input contains an integer T denoting the number of test cases.

The first line of each test case contains a single integer N denoting the number of integers in the array A.

The second line contains N space-separated integers A₁, A₂, …, A_N denoting the array A.

Output

For each test case, output a single line containing the answer.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ N, A[i] ≤ 10⁵

Subtasks

• Subtask #1 : (20 points) 1 ≤ N ≤ 100
• Subtask #2 : (80 points) Original constraints

Sample Input 1 

2
3
1 2 3
4
2 1 3 1

Sample Output 1 

1
2

Explanation

Example case 1. Let’s calculate prefixSum(i) + suffixSum(i) for all indexes i in the sample case.

prefixSum(1) + suffixSum(1) = 1 + 6 = 7
prefixSum(2) + suffixSum(2) = 3 + 5 = 8
prefixSum(3) + suffixSum(3) = 6 + 3 = 9

The minimum value of the function is 7, which is attained at index 1, so the answer would be 1.

Example case 2. Let’s calculate prefixSum(i) + suffixSum(i) for all indexes i in the sample case.

prefixSum(1) + suffixSum(1) = 2 + 7 = 9
prefixSum(2) + suffixSum(2) = 3 + 5 = 8
prefixSum(3) + suffixSum(3) = 6 + 4 = 10
prefixSum(4) + suffixSum(4) = 7 + 1 = 8

The minimum value of the function is 8, which is achieved for indices 2 and 4. The minimum of these two indices 2, 4 is index 2. Hence, the answer will be 2.

Little Chef and Sums CodeChef Solution in JAVA

import java.util.Scanner;
class Little_Chef_and_Sums {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        while (t-- > 0) {
            int n = input.nextInt();
            int arr[] = new int[n];
            int min = Integer.MAX_VALUE;
            int index = -1;
            for (int i = 0; i < n; i++) {
                arr[i] = input.nextInt();
                if (arr[i] < min) {
                    min = arr[i];
                    index = i;
                }
            }
            System.out.println(index + 1);
        }
        input.close();
    }
}

Little Chef and Sums CodeChef Solution in CPP

#include <iostream>
#include<bits/stdc++.h>
#define ll long long int
#include<algorithm>
using namespace std;
int main()
{
ll t;
cin>>t;
while(t--)
{
  ll n;
  cin>>n;
  ll arr[n];
  for(ll i=1;i<=n;i++)
  cin>>arr[i];
ll prevsum[n];
ll aftersum[n];
ll prefsum=0,sufsum=0;
  for(ll i=1;i<=n;i++)
  {
      prefsum+=arr[i];
      sufsum+=arr[n-i+1];
      prevsum[i]=prefsum;
      aftersum[i]=sufsum;
  }
//Indexing is one for now
ll minof=INTMAX_MAX,minindex=0;
for(ll i=1;i<=n;i++)
{
  if(prevsum[i]+aftersum[n-i+1]<minof)
  {  minof=prevsum[i]+aftersum[n-i+1];
      minindex=i;
  }
}
cout<<minindex<<endl;
}
      return 0;
}

Little Chef and Sums CodeChef Solution in Python

from sys import stdin
def main():
    T = int(stdin.readline().strip())
    for _ in range(T):
        N = int(stdin.readline().strip())
        liste = list(map(int, stdin.readline().strip().split()))
        a = min(liste)
        rep = liste.index(a)
        print(rep + 1)
if __name__ == "__main__":
    main()

Disclaimer: The above Problem (Little Chef and Sums) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purpose.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Chef and Mean Codechef Solution