dachivya
BAN USER- 0of 0 votes
AnswersAn additive sequence is 1,2,3,5,8,13
- dachivya in United States
where T(n) = T(n-1) + T(n-2)
An additive sequence number is which when splitted in two different number forms additive seq.
Ex: 1235813 (split it 1,2,3,5,8,13)
Ex: 12122436(12,12,24,36)
A number range is given to you. Find the additive sequence number in that range.| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm
Using double pointers only, will not solve this problem. There two types elements in the list; first are say, X which are not in loop and other say, Y, which belongs to loop.
let number of X are x. and number of Y are y.
And we need to calculate the x + y.
I will go with this approach:
First reverse the linked list and increment a counter, counter will be give you the value of 2x + y.
Now, using floyd cycle detection algo to find any Y. Calculate the value of y by just traversing the loop once starting from Y.
Calculate x + y, using prior equations.
Reverse again the linked list to give its original shape.
Total complexity should be O(n).
olution is quite complicated...but can work....
let first remove all the integral part of the elements so..
1.2 3.4 2.4
3.9 4.0 2.1
7.9 1.6 0.5
this left with
0.2 0.4 0.4 = 1 R1
0.9 0.0 0.1 = 1 R2
0.9 0.6 0.5 = 1+1 R3
------------ |
1+1 1 1 = 4
C1 C2 C3
and always sum of rows shud be equal to sum of columns..
now let the cell is Aij then check if Ri has how many number of 1's in it and correspondingly number of 1's in Cj. if both have atleast one number of 1's, then cancel one 1 from each of them and ceil Aij. else if any of the Ri or Cj has not have any 1 left then, floor it...its only a optimal solution using greedy approach...
But this would work in any case.
For having less memory solution, you can use memoziation by using circular array whose size should be 1+ maximum value of coin.
- dachivya August 12, 2012