C++ O(n) no extra space(no arry) solution with explaination


  • -8
    C

    Let's do this by cases.
    There are 3 cases.


    We call the result of multiplying all non-zero-numbers is "res".


    First, no zero in the list:

    Each number becomes "res" / itself.


    Second, only one zero in the list:

    Each number becomes zero except zero becoming "res"


    Third, two or more zeros in the list:

    Each number becomes zero

    class Solution {
    public:
    vector<int> productExceptSelf(vector<int>& nums) {
        long long res = 1;
        int i = 0;
        for (auto num: nums)
            if (num) res *= num;
            else i++;
        
        for (auto it = nums.begin(); it != nums.end(); it++) {
            if (i > 1) *it = 0;
            else if (i == 1) {
                if (*it == 0) *it = res;
                else *it = 0;
            }
            else *it = res / *it;
        }
        
        return nums;
        }
    };

  • 1
    C

    Did you notice that the problem said "Solve it without division" ??


Log in to reply
 

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