Skip to content

← leetcode

Replace Non Coprime Numbers in Array

· Hard

LeetCode problem 2197

The premise is simple. First, you unnecessarily define the Euclidean Algorithm because you forgot the gcd function exists:

private {
    int euclideanAlgorithm(int n1, int n2) {
        int remainder = -1;
        if (n2 > n1) swap(n1, n2);
        while (remainder != 0) {
            remainder = n1 - (n1/n2) * n2;
            n1 = n2;
            n2 = remainder;
        }
        return n1;
    }
}

Then, you initialize a stack...

vector<int> ans;
ans.push_back(nums[0]);

...and iterate through nums, checking if your current value is coprime to the top of the stack.

  • if it is, then you append to the stack.
  • if it is not, then you repeatedly update your current value to be the LCM between your current value and the top of the stack, pop the last element of the stack until either your stack is empty or your current value and the top of the stack is coprime. Now, you append your current value to the stack.
for (int i = 1; i < nums.size(); ++i) {
    int GCD = euclideanAlgorithm(ans.back(), nums[i]);
    if (GCD != 1) {
        int curr = static_cast<long long>(nums[i]) * ans.back() / GCD;
        ans.pop_back();
        while (!ans.empty() && GCD != 1) {
            GCD = euclideanAlgorithm(ans.back(), curr);
            if (GCD != 1) {
                curr = static_cast<long long>(curr) * ans.back() / GCD;
                ans.pop_back();
            }
        }
        ans.push_back(curr);
    } else {
        ans.push_back(nums[i]);
    }
}

Finally, you can be happy that you are free because this question was definitely not a hard difficulty question at all ahhhhhhh

return ans;

code

class Solution {
public:
    vector<int> replaceNonCoprimes(vector<int>& nums) {
        vector<int> ans;
        ans.push_back(nums[0]);
        for (int i = 1; i < nums.size(); ++i) {
            int GCD = euclideanAlgorithm(ans.back(), nums[i]);
            if (GCD != 1) {
                int curr = static_cast<long long>(nums[i]) * ans.back() / GCD;
                ans.pop_back();
                while (!ans.empty() && GCD != 1) {
                    GCD = euclideanAlgorithm(ans.back(), curr);
                    if (GCD != 1) {
                        curr = static_cast<long long>(curr) * ans.back() / GCD;
                        ans.pop_back();
                    }
                }
                ans.push_back(curr);
            } else {
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
private:
    int euclideanAlgorithm(int n1, int n2) {
        int remainder = -1;
        if (n2 > n1) swap(n1, n2);
        while (remainder != 0) {
            remainder = n1 - (n1/n2) * n2;
            n1 = n2;
            n2 = remainder;
        }
        return n1;
    }
};

complexity

  • Time: O(n log(m)) where n is the number of elements inside nums and m is the smallest digit inside nums (?)
    • the euclidean algorithm takes O(min(a, b)) so I am assuming m is just the smallest number inside nums
  • Space: O(n)

learnings

  • highkey, i forgot the gcd function existed
  • also, i am going to write the pseudocode for the algorithm before i code it from now on cuz i end up writing more code than i need

time taken

  • 15 minutes and 14 seconds