Reply to message- Messages should be written in English and correspond to the matter of the website.
- Messages should not contain offences and obscene words.
- Messages should not contain correct solutions.
Optimal solution Ok, just posting this to help others understand few things here: The sequence is 1101001000100000... If you see the locations of the digit 1, you can observe that it is at location 1,2,4,7...=> ( 1 + 0 ),( 1 + 1 ),( 1 + ( 1 + 2 )),( 1+(1+2+3 )..So, it is 1+sum_of_n_digits. What we have now is below: 1 + n*( n+1 )/2 [ note that n*(n+1)/2 is the sum of first n natural numbers ]. Now, this value should be equal to the input value, say P. 1 + n*(n+1)/2 = p [ I/p P=7 => n should be 3, back track ]. 2 + n^2 + n = 2p n^2 + n = 2(p-1) n^2 + n - 2 (p-1) = 0; This is a quadratic equation in 'n'. The roots of a quadratic equation are ( -b +- sqrt( b^2 - 4ac ) )/2a -1 +- sqrt( 8p-7 ) / 2; But, for our example, if you do some analysis, if the value of 8p-7 is a perfect square, then the value at that position 'p' would be 1. Else the value would be 0. So, check for 8p-7 to be a perfect square. This is the optimal solution. Got mine accepted. BTW, if you face any difficulty at test 3, it means you have to upgrade your ints to doubles. Because 8p-7 can falll over the size of int [atleast in Java]. Thanks, ElPsyCongroo.
|