Answer to Question #229090 in C for aman

Question

Harry loves numbers in the range [m1, m2] (m1 and m2 included). carry decides to gift harry an array of numbers for his birthday. harry wants to find the number of pairs of indices [l, r] for which the sum of all the elements in the range [l, r] lies between m1 and m2.   

1. Come up with an algorithm with a worst case complexity of O(N2).
2. Now improvise this algorithm, assuming all numbers are positive integers.  
3. What if the numbers could be negative as well? Can you think of an O(nlogn) solution in this case? (Hint: use sorting)  

Answer 1

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 6555
int main()
{
	//Algorithm time complexity O(n^2)
	printf("Please enter data:\n");
	int m1, m2;//Numbers that love Harry
	printf("m1:");
	scanf("%i", &m1);


	printf("m2:");
	scanf("%i", &m2);
	
	int n;//size array
	int ar[MAXSIZE];
	printf("Numbers count: ");
	scanf("%i", &n);
	printf("Please enter numbers:\n");
	for (int i = 0; i < n; i++)
		scanf("%i", &ar[i]);
	int cnt = 0;//number of pairs [l,r] l=0..n-1 r=0..n-1
	long long sum[MAXSIZE];
	for (int i = 0; i < MAXSIZE; i++)
		sum[i] = 0;
	//use prefix summ for example 1 2 3 =1 1+2 1+2+3=1 3 6....
	sum[0] = ar[0];
	for (int i = 1; i < n; i++)
		sum[i] = sum[i - 1] + ar[i];
	//find [l,r]
	for (int l = 0; l < n; l++)
	{
		for (int r = l; r < n; r++)
		{
			long long sums = sum[r] - sum[l] + ar[l];
			if (sums >=(long long) m1 && sums <=(long long) m2)
				cnt++;
		}
	}
	printf("Number pairs indices [l,r] wich sum [l,r] between m1 and m1: = %i\n", cnt);
	return 0;
}
/*


for example
m1=5
m2=6
ar[]=[1,2,3,4]
answer=2
1)1+2+3=6
2)2+3=5
5 and 6 between [5,6]
number pairs 2


*/