C++ 3-line O(k) Time O(1) Space Solution


  • 0
    F
    class Solution {
    public:
        vector<int> getRow(int n) {
            vector<int> result = {1};
            for (double i = 1; i <= n; ++i)
                result.push_back(result.back() * (n - i + 1) / i);
            return result;
        }
    };
    

  • 0
    S

    Weird thing is that your i is type double, and it indeed worked. I had the exact same approach as yours but with int type i in the for loop, and it doesn't pass.

    WHY!?


  • 0
    F

    I use double when I dealing operations with large number times/divided by numbers. It's just safer this way.
    One advantage of double in those cases is it is less likely to be overflowed.
    If you use "int" type, the intermediate number will be too large and overflow.
    I just tested "long" and it does work too. But still, I just blindly used double because it is safer and I don't really need worry about whether long or int is enough.


  • 0
    S

    @fentoyal Thank you for your reply, correct me if I am wrong.

    so, if i is "int", then

    result.back() * (n - i + 1) / i
    

    will overflow.

    But if i is "double", then by diving, the result is converted to double, which means the large number is safely stored.

    What you are doing is indeed a good programming habit, I just learnt something today, thanks!


  • 1
    F

    @SebastianZhou
    Actually, we probably can guarantee the number AFTER dividing should never overflow, because OJ provided a vector of INT to store the results. So the reason is not about the number AFTER dividing.
    I chose double because there is an intermediate (temporary) number -- the product of result.back() * (n - i + 1) -- this one is BEFORE dividing, and can easily overflow. Using double can handle this corner case.

    A simpler example can be like this: we know INT_MAX is 2147483647
    now you let a = 2147483647;
    If you do something like b= a * 2 / 4 (without a smart compiler that will deduce it to a / 2 in compile time), you won't get right result, because a * 2 overflows and becomes some negative number, and then this negative number is divided by 4.
    Using double or long or long long can avoid this problem. This is some trick I learned over time too.


  • 0
    C

    i have a diffrent with you,I put i ahead,to ensure it not overflowed,
    result.back() / i * (n - i + 1)
    then ,I am wrong,why?


  • 0
    F

    @chenpuyang
    Is your i double too?
    And then try wrapping the expression with a "round()" function.
    10/9 * 9 is just 9.999..9. so int k = 10/9 * 9, k will be floored to 9 instead of 10.
    Lastly, I'm glad to help. But I want to mention, debugging skill is also evaluated in an interview, so I suggest you to try figuring things like this out by yourself first. It is also a good practice.


  • 0
    C

    @fentoyal
    Thanks,I understand,and I'll try by myself.


Log in to reply
 

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