@vaibhavahuja1 You made a very silly mistake. Your output string has spaces between the digits.
For input,
1
4 12
your output is:
1 1 0 2 0 1 1 0 0 1 1 0
Somebody please help me. PLEASE!!
I thought of the following solution. Plz can someone tell me if it is valid and can be implemented without getting a tle:
- Find the sum and check if it is possible to divide the numbers into two sets of equal sums.
- If possible, then we start with an array of numbers from 1 to n.
- We put the first and last numbers in one set and the second and second last numbers in second set and we skip the number x.
- We maintain two sum counts for each set. We check after the above division if thw two sums are equal or not.
- If equal we have the division. If not then, there are 2 cases. We calculate the difference between the required sum and the set with the smaller sum. If the number equal to the difference is present in the set then we can add it in the set. If not then we find the number from the smaller set to be swapped with a number in the larger set.
How did you came up with this solution? How did you made all those cases separately?
you call case “8 11” impossible - it isn’t, eg. 10000012011
1 Like
You can step almost directly to the right place to split the set by calculating the triangular number closest above the partition totals. Then with only a small adjustment of one to three elements, you can get a qualifying partition without intermediate calculation.
Kudos to the test case writer for finding “4 4” to break my first submission - the partition total is 3, which is less than 4 (my test) but not less than the highest remaining element. D’oh.