O(LogN) is possible?


  • 2

    The answer of this question could be calculated in this way:

    Sum ( the kth Fibonacci number * 2 ^ (n+1-k) ) with k=1 to n+1
    

    The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13.....

    For examples:

    N = 2
    Answer = 1 * 4 + 1 * 2 + 2 * 1 = 8
    
    N = 3
    Answer = 1 * 8 + 1 * 4 + 2 * 2 + 3 * 1 = 19
    
    N = 4
    Answer = 1 * 16 + 1 * 8 + 2 * 4 + 3 * 2 + 5 * 1 = 43
    
    N = 5
    Answer = 1 * 32 + 1 * 16 + 2 * 8 + 3 * 4 + 5 * 2 + 8 * 1 = 94
    

    I didn't chance upon the rule and the strict demonstration is not complex, but it is not my point. If you have any doubts, please point out the reason.

    The general formula of Fibonacci is here: https://en.wikipedia.org/wiki/Fibonacci_number

    The general formula of Geometric progression: https://en.wikipedia.org/wiki/Geometric_progression

    Finally we can get the general formula of these question after some math evolution.

            n = n + 1
            a = (1 + 5**0.5) / 4
            b = (1 - 5**0.5) / 4
            res = 2**n / 5**0.5 * ((1 - a**n) / (1 - a) * a - (1 - b**n) / (1 - b) * b)
    

    Unfortunately, the float is too long to keep accurate.


  • 1

    @lee215 said in O(LogN) is possible?:

    The answer of this question could be calculated in this way:

    Sum ( the kth Fibonacci number * 2 ^ (n-k) ) with k=1 to n
    

    Nah, doesn't work.


  • 0

    @StefanPochmann I modified n to n+1 and it does work.


  • 0

    @lee215 No it doesn't.


  • 0

    I see you edited some more, now really fixing that uninteresting off-by-one error. But it still doesn't work, as the main error is still there. It works until n = 5 (not "N", btw) but fails for n = 6 and higher. Submitting it would've shown that to you.

    Can you fix it? Maybe it's possible, but I don't see how. Can't find the mistake in your reasoning if I don't know your reasoning.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.