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.
Come up with an algorithm with a worst case complexity of O(N2).
Now improvise this algorithm, assuming all numbers are positive integers.
What if the numbers could be negative as well? Can you think of an O(nlogn) solution in this case? (Hint: use sorting)
For this task you are asked to write a program that consists of a le recap.cpp and a
makele to compile and run it. You will need to include a blank data.txt le in your
submission as well. Your makefille must compile the executable as main. You are required to read this data, line by line, into a 2D dynamic array of strings.
The format of the line is as follows:
1,a,b,c,d
Each line starts with an ID, which is an int, and then will be followed by an unknown
number of strings separated by commas. Each string in the line is associated with the ID
of the line. Each line will have at least the ID and 1 item.
Once the items are stored in the array you need to print out the array in ascending order
based on the order IDs in the following format:
ID,a,b,c
An example of this output is as follows (for 2 orders):
3,toaster,iron
4,spanner,wrench,hammer
Terminate each line of output with a newline.
The following libraries are allowed:
- iostream
- fstream
- string
- sstream