Efficient Algorithms to Compute The kth Factor of a Natural Numb
- Time:2020-09-07 13:13:13
- Class:Weblog
- Read:33
Given two positive integers n and k. A factor of an integer n is defined as an integer i where n % i == 0. Consider a list of all factors of n sorted in ascending order, return the kth factor in this list or return -1 if n has less than k factors.
Example 1:
Input: n = 12, k = 3
Output: 3
Explanation: Factors list is [1, 2, 3, 4, 6, 12], the 3rd factor is 3.Example 2:
Input: n = 7, k = 2
Output: 7
Explanation: Factors list is [1, 7], the 2nd factor is 7.Example 3:
Input: n = 4, k = 4
Output: -1
Explanation: Factors list is [1, 2, 4], there is only 3 factors. We should return -1.Example 4:
Input: n = 1, k = 1
Output: 1
Explanation: Factors list is [1], the 1st factor is 1.Example 5:
Input: n = 1000, k = 3
Output: 4
Explanation: Factors list is [1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100, 125, 200, 250, 500, 1000].Constraints:
1 <= k <= n <= 1000Hints:
The factors of n will be always in the range [1, n].
Keep a list of all factors sorted. Loop i from 1 to n and add i if n % i == 0. Return the kth factor if it exist in this list.
O(N) Bruteforce Algorithm to Compute The kth Factor of N
Let’s try from 1 to N and check if it is divisible. Return the Kth factor if exists:
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: int kthFactor(int n, int k) { for (int i = 1; i <= n; ++ i) { if (n % i == 0) { k --; if (k == 0) return i; } } return -1; } }; |
class Solution { public: int kthFactor(int n, int k) { for (int i = 1; i <= n; ++ i) { if (n % i == 0) { k --; if (k == 0) return i; } } return -1; } };
We can optimise the solution to O(N/2) as apparently there are no factor between number N/2+1 to N-1.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: int kthFactor(int n, int k) { for (int i = 1; i<= n / 2; ++ i) { if (n % i == 0) { k --; if (k == 0) return i; } } return k == 1 ? n : -1; } }; |
class Solution { public: int kthFactor(int n, int k) { for (int i = 1; i<= n / 2; ++ i) { if (n % i == 0) { k --; if (k == 0) return i; } } return k == 1 ? n : -1; } };
The solution is still linear but the implementation will be faster than the first version of the bruteforce.
O(Sqrt(N)) Optimised Bruteforce Algorithm to Compute The kth Factor of N
We know for every factor d, there will be a pair factor n/d except when d*d == n. Thus, we have to only check from 1 to Sqrt(N), and take care of the specical case when d*d==N. Two loops of O(Sqrt(N)). First iterate from 1 to Sqrt(N), and then downwards to 1 i.e. n/i.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | class Solution { public: int kthFactor(int n, int k) { int d = 1; for (; d * d <= n; ++ d) { if (n % d == 0) { if (-- k == 0) { return d; } } } for (d = d - 1; d >= 1; -- d) { if (d * d == n) continue; if (n % d == 0) { if (-- k == 0) { return n / d; } } } return -1; } }; |
class Solution { public: int kthFactor(int n, int k) { int d = 1; for (; d * d <= n; ++ d) { if (n % d == 0) { if (-- k == 0) { return d; } } } for (d = d - 1; d >= 1; -- d) { if (d * d == n) continue; if (n % d == 0) { if (-- k == 0) { return n / d; } } } return -1; } };
The algorithm complexity is O(Sqrt(N)).
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:Wondrous Xinjiang: Populus euphratica forests attract tourists w
Chinese shipbuilders seek transition towards clean energy
China beats Vietnam to win 2024 CFA Team China Int'l Women's Foo
U.S. "deeply troubled" by Israeli legislation banning UNRWA: spo
Fujian's Zhangzhou sees prospering development of fishing-touris
Population of milu deer increases due to conservation efforts in
Autumn harvest in full swing in China
Hainan responds to extensive flooding
China mulls law revision to better protect maritime passengers
Shenzhou-18 mission returns samples for extraterrestrial habitat
- Comment list
-
- Comment add