using System;

using System.Linq;

using System.Collections.Generic;

using System.Text;

​

/*

​

**************** This is optimized Solution (UNDER CONSTRUCTION) *****************

​

Link: [https://www.scaler.com/academy/mentee-dashboard/class/26749/assignment/problems/4116?navref=cl_tt_nv]

Problem Description

​

Given an array of positive integers A and an integer B, find and return first continuous subarray which adds to B.

​

If the answer does not exist return an array with a single element "-1".

​

First sub-array means the sub-array for which starting index in minimum.

​

​

​

Problem Constraints

1 <= length of the array <= 100000

1 <= A[i] <= 109

1 <= B <= 109

​

​

​

Input Format

The first argument given is the integer array A.

​

The second argument given is integer B.

​

​

​

Output Format

Return the first continuous sub-array which adds to B and if the answer does not exist return an array with a single element "-1".

​

​

​

Example Input

Input 1:

​

 A = [1, 2, 3, 4, 5]

 B = 5

Input 2:

​

 A = [5, 10, 20, 100, 105]

 B = 110

​

​

Example Output

Output 1:

​

 [2, 3]

Output 2:

​

 -1

​

​

Example Explanation

Explanation 1:

​

 [2, 3] sums up to 5.

Explanation 2:

​

 No subarray sums up to required number.

​

*/                  

public class Program

{

    private static List<int> solve(List<int> A, int B)

    {

        int listCount = A.Count;

        List<long> prefixSumList = new List<long>();

        List<int> resList = new List<int>();

        int sumIndex = -1;

        //Do Iterate and store the prefix sum

        long tmpSum = 0;

        for(var i = 0; i < listCount; i++){

            tmpSum += A[i];

            prefixSumList.Add(tmpSum);

            if(tmpSum == B){

                sumIndex = i;

                break;

            }

        }

        //

        if(sumIndex == -1){

            resList.Add(-1);

        }else{

            for(var j = 0; j < (sumIndex + 1); j++){

                resList.Add(A[j]);

            }

        }

        return resList;

    }

    public static void Main()

    {

        /*List<int> sumToFindList = new List<int>() { 0, 0, 2, 2 };

        int sumToFind = 4;*/

        List<int> sumToFindList = new List<int>() { 5, 10, 20, 100, 105 };

        int sumToFind = 110;

        List<int> sumAfterFindFromList = Program.solve(sumToFindList, sumToFind);

        Console.WriteLine("Contiguous sum is : " + string.Join(" ", sumAfterFindFromList));

    }

}