i made a code for GUZAC. i first got an array of exactly known elements. got it sorted. found if the max diff b/w known elements is less than given max diff. if yes then made a temp variable which stored (max_diff+arr[0]-since array is sorted arr[0] is smallest). then started decreasing temp and simultaneously checked whether it was already present in known arr or not. similar logic for the other case. however this gives me a TLE error. what changes can i make into my code(i thought only sorting would take time else everything is done in almost constant time. since the c++ stl’s sort is having time complexity O(nlog(n)) it should have been well within the time limits.
the link to my code can be found here. Thanks in advance.
Refer to editorial. If the array is sorted, the numbers lying between A[i] and A[i+1] can all be chosen. Find formula to add these numbers in O(1) time, instead of adding one element at a time.
Sorting has to be done… What my suggestion is suppose given array is 1,101 ,201, 1001 (after sorting) and x=2000
then append (1+2000)+1=2002 to this array
So it will be 1, 101, 201, 1001, 2002
Now in your algo I guess you will start from 2001 and go till 1 or till you get sum linearly… #what you can actually optimize is break sum into parts till you get n elements as follows… sum(1002,2001)+sum(202,1000)+sum(102,200)+sum(100,2)
where sum(x,y) denotes sum of x + (x+1) + (x+2) + (x+3) + .... + y sum(x,y) can be computed in O(1) using formula of summation of 1 to n
##HERE is a refernce link if you don’t know how to compute that…
Obviously you need to stop sum before n exceeds as you need only n numbers…
which is easy to implement… just keep subtracting (y-x+1) from n each time you add sum…
