Please help me debug the code for Anurag And Squares Question Here ; My solution giving WA
Please help me find a test case that will give WA on my code, or explain to me why this logic will not work, and correct approach if my solution is completely wrong.
Hey for input:37 output should be 26 but your code gives 42.
Your approach is incorrect . check this for correct approach https://math.stackexchange.com/questions/214234/tiling-a-minimal-perimeter-region-with-n-unit-squares
Try this test case:
Expected output: 16
Your code gives: 18
Correct approach(for numbers which are not perfect squares):
Consider 2 numbers a and b which are perfect squares such b>a and b is the immediate perfect square after a. There are exactly 2*sqrt(a) numbers between a and b. If we consider the first sqrt(a) numbers after a and arrange that many number of squares, they will have a minimum perimeter equal to 2 plus the minimum perimeter of a squares when they are arranged. Similarly, when the next sqrt(a) numbers after a are arranged in terms of squares, they will have a minimum perimeter equal to 4 plus the minimum perimeter of a squares when they are arranged.
The following solution works completely fine:
else if((m-n)<=sqrt(n)) //the first sqrt(n) numbers after n
else //the next sqrt(n) numbers after n
Consider the test case 13
Thus, ans = 4*sqrt(n)+4 = 4*3+4 = 16