HardNo. 2197
Replace Non-Coprime Numbers in Array — LeetCode 2197 Python Solution
- Pattern
- Stack
- Topics
- Stack, Array, Math, Number Theory
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You are given an array of integers nums. Perform the following steps: Find any two adjacent numbers in nums that are non-coprime.
Example
- Input
- nums = [6,4,3,2,7,6,2]
- Output
- [12,7,6]
- Explanation
- - (6, 4) are non-coprime with LCM(6, 4) = 12. Now, nums = [12,3,2,7,6,2].
Python solution
class Solution:
def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
stk = []
for x in nums:
stk.append(x)
while len(stk) > 1:
x, y = stk[-2:]
g = gcd(x, y)
if g == 1:
break
stk.pop()
stk[-1] = x * y // g
return stkComplexity
- Time
- O(n × log M)
- Space · auxiliary
- O(n)
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 2197. Replace Non-Coprime Numbers in Array is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Stack.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0150 | Evaluate Reverse Polish Notation | Medium |
| 0042 | Trapping Rain Water | Hard |
| 0224 | Basic Calculator | Hard |
| 0227 | Basic Calculator II | Medium |
| 0321 | Create Maximum Number | Hard |
| 0445 | Add Two Numbers II | Medium |
Frequently asked questions
- How hard is LeetCode 2197. Replace Non-Coprime Numbers in Array?
LeetCode 2197. Replace Non-Coprime Numbers in Array is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2197. Replace Non-Coprime Numbers in Array?
The Python solution on this page runs in O(n × log M).
- What is the space complexity of LeetCode 2197. Replace Non-Coprime Numbers in Array?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 2197. Replace Non-Coprime Numbers in Array cover?
LeetCode 2197. Replace Non-Coprime Numbers in Array is tagged Stack, Array, Math and Number Theory on LeetCode.