Official algorithmic problem description and constraints.
GCD (Greatest Common Divisor) of two integers π₯ and π¦ is the maximum integer π§ by which both π₯ and π¦ are divisible. For example, πΊπΆπ·(36,48)=12, πΊπΆπ·(5,10)=5, and πΊπΆπ·(7,11)=1.
Kristina has an array π consisting of exactly π positive integers. She wants to count the GCD of each neighbouring pair of numbers to get a new array π, called GCD-sequence.
So, the elements of the GCD-sequence π will be calculated using the formula ππ=πΊπΆπ·(ππ,ππ+1) for 1β€πβ€πβ1.
Determine whether it is possible to remove exactly one number from the array π so that the GCD sequence π is non-decreasing (i.e., ππβ€ππ+1 is always true).
For example, let Khristina had an array π = [20,6,12,3,48,36. If she removes π4=3 from it and counts the GCD-sequence of π, she gets:
The resulting GCD sequence π = [2,6,12,12] is non-decreasing because π1β€π2β€π3β€π4.
Detailed video explanations, mathematical intuition, and clean C++ implementation code.
