This question came in Codechef September Long Challenge, hope you find this solution useful.
PROBLEM STATEMENT:
You are given a positive integer N. Consider the sequence S=(1,2,…,N). You should choose two elements of this sequence and swap them.
A swap is nice if there is an integer M (1≤M<N) such that the sum of the first M elements of the resulting sequence is equal to the sum of its last N−M elements. Find the number of nice swaps.
BRUTE FORCE APPROACH
Firstly, find the total sum of the given array, if the sum is odd, then simply return 0, as there is no possibility to divide that array into equal half.
Now, check for the second case, when the sum is even:
Iterate through the array, and calculate the sum of elements of the subarray, till it would be less than on equal to half sum.
Then calculate the number of swaps.
Swaps = xC2(For first partition) + n-xC2(For second partition) + n-x(For swaps in between two partitions)
This approach will give you TLE, as finding the sum of the array through iteration will take O(n) time, which can be reduced to O(1).
Optimised Approach
- Find the total sum as (n*(n+1))/2 .
- Check if it is even or odd, if odd, return 0, else proceed to the next step.
- Now, we will calculate the sum of subarray having sum approximately half of the total sum.
This is the main logic of finding a sum in this question.
Look at the following mathematics using Shri Dhanacharya equation:
It will give the element up to which the sum of the subarray is approximately half of the total sum in O(1) time complexity.
fquad == quad means both the subarray have sum exactly half of the total sum, if this condition is false, the sub sum is not exactly half of the total sum, hence we need to swap elements, hence on n-x swaps would be counted.
I hope you found this editorial helpful, please give me a like and follow me.
Happy coding :)
Top comments (0)