Tap here to switch tabs
Problem
Submissions

Problem: GCD Sort of an Array

GCD Sort of an Array asks whether an integer array can be sorted in ascending order using swaps only between pairs whose greatest common divisor exceeds one.

Statement

Given an integer array nums, you are permitted to swap the elements at any two distinct indices i and j if and only if the greatest common divisor of nums[i] and nums[j] is strictly greater than 11. That is, gcd⁡(‘nums[i]‘,‘nums[j]‘)>1\gcd(`nums[i]`, `nums[j]`) > 1.

You may perform this swap operation any number of times.

Return true if it is possible to sort nums in ascending order, or false otherwise.

Constraints:

  • 1≤1 \leq nums.length ≤3×104\leq 3 \times 10^4

  • 2≤2 \leq nums[i] ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: GCD Sort of an Array

GCD Sort of an Array asks whether an integer array can be sorted in ascending order using swaps only between pairs whose greatest common divisor exceeds one.

Statement

Given an integer array nums, you are permitted to swap the elements at any two distinct indices i and j if and only if the greatest common divisor of nums[i] and nums[j] is strictly greater than 11. That is, gcd⁡(‘nums[i]‘,‘nums[j]‘)>1\gcd(`nums[i]`, `nums[j]`) > 1.

You may perform this swap operation any number of times.

Return true if it is possible to sort nums in ascending order, or false otherwise.

Constraints:

  • 1≤1 \leq nums.length ≤3×104\leq 3 \times 10^4

  • 2≤2 \leq nums[i] ≤105\leq 10^5