花花酱 LeetCode 1998. GCD Sort of an Array

By zxi on December 31, 2021

You are given an integer array nums, and you can perform the following operation any number of times on nums:

Swap the positions of two elements nums[i] and nums[j] if gcd(nums[i], nums[j]) > 1 where gcd(nums[i], nums[j]) is the greatest common divisor of nums[i] and nums[j].

Return true if it is possible to sort nums in non-decreasing order using the above swap method, or false otherwise.

Example 1:

Input: nums = [7,21,3]
Output: true
Explanation: We can sort [7,21,3] by performing the following operations:
- Swap 7 and 21 because gcd(7,21) = 7. nums = [21,7,3]
- Swap 21 and 3 because gcd(21,3) = 3. nums = [3,7,21]

Example 2:

Input: nums = [5,2,6,2]
Output: false
Explanation: It is impossible to sort the array because 5 cannot be swapped with any other element.

Example 3:

Input: nums = [10,5,9,3,15]
Output: true
We can sort [10,5,9,3,15] by performing the following operations:
- Swap 10 and 15 because gcd(10,15) = 5. nums = [15,5,9,3,10]
- Swap 15 and 3 because gcd(15,3) = 3. nums = [3,5,9,15,10]
- Swap 10 and 15 because gcd(10,15) = 5. nums = [3,5,9,10,15]

Constraints:

1 <= nums.length <= 3 * 10⁴
2 <= nums[i] <= 10⁵

Solution: Union-Find

Let nums[j]’s target position be i. In order to put nums[j] to pos i by swapping. nums[i] and nums[j] must be in the same connected component. There is an edge between two numbers if they have gcd > 1.

We union two numbers if their have gcd > 1. However, it will be TLE if we do all pairs . Thus, for each number, we union it with its divisors instead.

Time complexity: O(n²) TLE -> O(sum(sqrt(nums[i]))) <= O(n*sqrt(m))
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

bool gcdSort(vector<int>& nums) {

const int m = *max_element(begin(nums), end(nums));

const int n = nums.size();

vector<int> p(m + 1);

iota(begin(p), end(p), 0);

function<int(int)> find = [&](int x) {

return p[x] == x ? x : (p[x] = find(p[x]));

};

for (int x : nums)

for (int d = 2; d <= sqrt(x); ++d)

if (x % d == 0)

p[find(x)] = p[find(x / d)] = find(d);

vector<int> sorted(nums);

sort(begin(sorted), end(sorted));

for (int i = 0; i < n; ++i)

if (find(sorted[i]) != find(nums[i]))

return false;

return true;

}

};

花花酱 LeetCode 1952. Three Divisors

By zxi on December 31, 2021

Given an integer n, return true if n has exactly three positive divisors. Otherwise, return false.

An integer m is a divisor of n if there exists an integer k such that n = k * m.

Example 1:

Input: n = 2
Output: false
Explantion: 2 has only two divisors: 1 and 2.

Example 2:

Input: n = 4
Output: true
Explantion: 4 has three divisors: 1, 2, and 4.

Constraints:

1 <= n <= 10⁴

Solution: Enumerate divisors.

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isThree(int n) {

int c = 0;

for (int i = 1; i <= n; ++i)

if (n % i == 0) ++c;

return c == 3;

}

};

Optimization

Only need to enumerate divisors up to sqrt(n). Special handle for the d * d == n case.

Time complexity: O(sqrt(n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isThree(int n) {

int c = 0;

for (int i = 1; i <= sqrt(n); ++i)

if (n % i == 0)

c += 1 + (i * i != n);

return c == 3;

}

};

花花酱 LeetCode 1390. Four Divisors

By zxi on March 22, 2020

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

1 <= nums.length <= 10^4
1 <= nums[i] <= 10^5

Solution: Math

If a number is a perfect square (e.g. 9 = 3 * 3), it will have odd number of divisors. (9: 1, 3, 9).

Time complexity: O(sum(sqrt(num_i))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int sumFourDivisors(vector<int>& nums) {

int ans = 0;

for (int n : nums) {

int r = sqrt(n);

if (n <= 4 || r * r == n) continue;

int count = 2;

int sum = 1 + n;

for (int d = 2; d <= r; ++d)

if (n % d == 0) {

count += 2;

sum += n / d + d;

}

if (count == 4) ans += sum;

}

return ans;

}

};

花花酱 LeetCode 1362. Closest Divisors

By zxi on February 23, 2020

Given an integer num, find the closest two integers in absolute difference whose product equals num + 1 or num + 2.

Return the two integers in any order.

Example 1:

Input: num = 8
Output: [3,3]
Explanation: For num + 1 = 9, the closest divisors are 3 & 3, for num + 2 = 10, the closest divisors are 2 & 5, hence 3 & 3 is chosen.

Example 2:

Input: num = 123
Output: [5,25]

Example 3:

Input: num = 999
Output: [40,25]

Constraints:

1 <= num <= 10^9

Solution: Brute Force

Time complexity: O(sqrt(n))
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<int> closestDivisors(int num) {

auto divisors = [](int n) {

for (int i = sqrt(n); i >= 2; --i)

if (n % i == 0) return vector<int>{i, n / i};

return vector<int>{1, n};

};

auto ans1 = divisors(num + 1);

auto ans2 = divisors(num + 2);

return ans1[1] - ans1[0] < ans2[1] - ans2[0] ? ans1 : ans2;

}

};

Python3

# Author: Huahua

class Solution:

def closestDivisors(self, num: int) -> List[int]:

def divisors(n: int) -> List[int]:

for i in range(int(math.sqrt(n)), 1, -1):

if n % i == 0: return [i, n // i]

return [1, n]

a1, a2 = divisors(num + 1), divisors(num + 2)

return a1 if a1[1] - a1[0] < a2[1] - a2[0] else a2

花花酱 LeetCode 633. Sum of Square Numbers

By zxi on August 22, 2018

Problem

Given a non-negative integer c, your task is to decide whether there’re two integers a and b such that a² + b² = c.

Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

Solution: Math

Time complexity: O(sqrt(c))

Space complexity: O(1)

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

bool judgeSquareSum(int c) {

int m = sqrt(c);

for (int a = 0; a <= m; ++a) {

int b = round(sqrt(c - a * a));

if (a * a + b * b == c) return true;

}

return false;

}

};

Posts tagged as “sqrt”

花花酱 LeetCode 1998. GCD Sort of an Array

Solution: Union-Find

C++

花花酱 LeetCode 1952. Three Divisors

Solution: Enumerate divisors.

C++

Optimization

C++

花花酱 LeetCode 1390. Four Divisors

Solution: Math

C++

花花酱 LeetCode 1362. Closest Divisors

Solution: Brute Force

C++

Python3

花花酱 LeetCode 633. Sum of Square Numbers

Problem

Solution: Math