NXS4-Editorial

PROBLEM LINK:

Practice

Author: Setter’s name
Tester: Tester’s name
Editorialist: Editorialist’s name

DIFFICULTY:

SIMPLE, EASY

PREREQUISITES

Array prefix sum.

PROBLEM:

Problem statement simply says that given an array of N elements we need to answer Q query in every query you need to print the sum of the elements between the given range (Xi, Yi)

EXPLANATION:

1st solution may lead you towards TLE. If we just start a loop from X to Y and take the sum of every element and print sum after the loop will give you AC but this is not an optimal solution and give you TLE.
Time complexity for this solution is O( Q * (Y-X) ) we can say O(N2) time complexity.

Let’s see an optimal solution. We need to go for an array prefix sum method. We first need to create an array with prefix sum then for every query we can just print ar[Y-1]-ar[X-2] which will give sum between given range but we need to take care of X==1 this may lead to Runtime Error so if x==1 print ar[Y-1]. Time compexity for this solution will be O(Q).

Users, please use fast IO hence test-case file size is large

For more clarification refer to my solution

SOLUTIONS:

Editorialist's Solution
import java.util.Scanner;
import java.io.*;

class NXS4 {
	public static void main (String[] args)throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	int test = Integer.parseInt(br.readLine());
	while(test-->0){
	    String i1[] = br.readLine().split(" ");
	    int n = Integer.parseInt(i1[0]);
	    int q= Integer.parseInt(i1[1]);
	    
	    String s[]= br.readLine().split(" ");
	    long ar[]=new long[n];
	    for(int i=0;i<n;i++){
	    ar[i]=Long.parseLong(s[i]);
	    }
	    
	    //prefix sum
	    for(int i=1;i0){
	        String i2[]= br.readLine().split(" ");
	        int l = Integer.parseInt(i2[0]);
	        int r = Integer.parseInt(i2[1]);
	        if(l==1)
	        System.out.println(ar[r-1]);
	        else
	        System.out.println(ar[r-1]-ar[l-2]);
	    }
	    
	}
	        
    }
}

Feel free to share your approach, if you want to. (even if it’s same) . Suggestions are welcomed as always had been.