Just wanted to do some program in SPOJ for fun. But thought of what is fun in doing simple one. Tried this program.
It was interesting, fun and learning.
Started with simple method to find the sum of 1st in binary form.
Tried to see the pattern. Printed like pattern to see how sum of 1's is actually changing. is there any pattern to use.
Could not find any pattern.
time taken for a 100000000 to 200000000 0.8sec
Created hash map for 1 byte to number of 1's.
created methods to calculate sum-of-1's using the hash map.
created multiple methods, that has reduced time to 0.68sec.
After that realized, instead of doing the loop with 256 times.
we can just count number of bytes which result in sum of 1's as 0, 1, 2, 3, 4, 5, 6, 7, 8.
10^19 fits in 64 bits, so has to use unsigned long long.
2^64 > 10^19 but 2^63 < 10^19.
realized the sum could not be more than 64.
So lucky numbers possible are 4, 7, 44, 47 (not possible 74, 77...)
Using this map made it work for last byte.
It was time taking.
There is huge gap between 7 and 44, using this tried to avoid some places where there could be no possibility of getting a lucky number.
Next taken it to 2 bytes level.
generated the bit sum histogram for 2 bytes.
Realized there is a semmitry.
Next to 3 bytes and bit-sum-histogram for 3 bytes.
Realized this is nothing but 24C0, 24C1....24C24.
Next to 4 bytes level did using nCr formula. But the multiplication has overflowed, for 3 numbers 24C14, 24C15, 24C16.
Corrected them from Wolfram Alpha.
The time was 0.0 sec execution time.
But still stuck in loop for large inputs.
Next to 5 bytes level, instead of writing same function again and again, made the generation function generic.
Felt you can create these tables (nCr) using additions and histograms, without multiplications and divitions.
So on created till 7byte level.
Changed the algorithm for 1 byte level different way and rest is by calling lower level for some and some part in the main.
The answer was wrong. So checked the generated values using
But the problem was the algo did not handle the upper level smaller blocks.
Later properly divided the range in 3 ranges.
prefix range that need to be handled 1 byte less level.
postfix range also the same way.
next the middle one by using the calculate histogram and checking for lucky number.
But still there were problems with close a and b. The 3 ranges I was using had some problems.
inputs like
1 999 1000 used to give wrong answers.
toolkit was useful, in getting these negetive cases.
This input showed me the flaw in my range divisions.
Input:
4
1 1000000000000000000
100000000000000000 1000000000000000000
999999999999999999 1000000000000000000
999999999999 99999999999999999
My Output:
87909819571418
87168839904896
16811633173286
740960940299
Expected:
87909819571418
87168839904896
0
740960940299
Used this one to debug.
1
999999999999999999 1000000000000000000
found it was giving error for simple case also.
1
999 1000
Fixed those cases of range miss-match.
Finally got the answer correct.
This took the whole day today. In the middle realised, I lost touch of problem solving. It was like flow. I did not felt hungry for long time, because I was involved in solving it. The involvement gave me the happiness.