Finding the Closest Divisors
- Time:2020-09-10 13:27:27
- Class:Weblog
- Read:42
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^9Hints:
Find the divisors of n+1 and n+2.
To find the divisors of a number, you only need to iterate to the square root of that number.
Find the divisors of n+1 and n+2
We can find the closet divisors for n+1 and n+2 respectively. Then, we can compare the absolute difference of both divisors and pick the smaller one.
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: vector<int> closestDivisors(int num) { vector<int> r1 = findDivisor(num + 1); vector<int> r2 = findDivisor(num + 2); if (abs(r1[0] - r1[1]) < abs(r2[0] - r2[1])) { return r1; } return r2; } private: vector<int> findDivisor(int num) { vector<int> r = {1, num}; for (int i = 2; i * i <= num; ++ i) { if (num % i == 0) { r = {i, num / i}; } } return r; } }; |
class Solution { public: vector<int> closestDivisors(int num) { vector<int> r1 = findDivisor(num + 1); vector<int> r2 = findDivisor(num + 2); if (abs(r1[0] - r1[1]) < abs(r2[0] - r2[1])) { return r1; } return r2; } private: vector<int> findDivisor(int num) { vector<int> r = {1, num}; for (int i = 2; i * i <= num; ++ i) { if (num % i == 0) { r = {i, num / i}; } } return r; } };
We can start from the square root in the non-ascending order, thus enabling us early exit if we find a divisor. An improvement is to check (x+1) first then (x+2) since the first found divisor is the answer, we can safely exit the loop.
1 2 3 4 5 6 7 8 9 10 11 12 | class Solution { public: vector<int> closestDivisors(int x) { for (int a = sqrt(x + 2); a > 0; --a) { if ((x + 1) % a == 0) return {a, (x + 1) / a}; if ((x + 2) % a == 0) return {a, (x + 2) / a}; } return {}; } }; |
class Solution { public: vector<int> closestDivisors(int x) { for (int a = sqrt(x + 2); a > 0; --a) { if ((x + 1) % a == 0) return {a, (x + 1) / a}; if ((x + 2) % a == 0) return {a, (x + 2) / a}; } return {}; } };
Only the divisors up to Square Root of N are checked thus the runtime complexity of above solutions are O(Sqrt(N)).
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:How to Make Money from Blogging as a Small Business
6 Reasons Why Your WordPress Blog Is Getting Hacked
When to Revise Your Content Marketing Strategy
How To Develop Copywriting Skills To Engage Your Blog Readers
Five Tips to Lower Your Tax Bill in 2020
Bruteforce Algorithm to Compute the Maxmium Powerful Digit Sum u
4 Frequently Discussed SEO Myths Exposed
3 Reasons Why Graphic Designers Need to Self-Promote through Ins
How to Split a String in C++?
The Best Instagram Feed WordPress Plugins to Use
- Comment list
-
- Comment add