Closest Divisors ใน C++ : หาตัวหารคู่ที่ใกล้ที่สุดของ num+1 หรือ num+2

ให้ Integer num หา **คู่ตัวหาร (a, b)** ที่:

• a * b = num + 1 **OR** a * b = num + 2
• |a - b| **น้อยที่สุด** (Closest Divisors)

คืนค่าคู่ที่ดีกว่า (Diff น้อยกว่า) ใดก็ได้

ตัวอย่าง

num = 8

• num+1 = 9: Divisors (1,9) Diff=8, (3,3) Diff=0 -> **Best: (3,3)**
• num+2 = 10: Divisors (1,10) Diff=9, (2,5) Diff=3 -> Best: (2,5)

เลือก (3,3) เพราะ Diff=0 < 3

Output: [3, 3]

แนวทาง: หาตัวหารคู่ที่ใกล้ที่สุดของจำนวนหนึ่ง (getDiv)

สำหรับจำนวน x หา a, b ที่ a*b=x และ |a-b| Min:

• Loop i = 1 .. sqrt(x)
• ถ้า x % i == 0 -> Candidate (i, x/i)
• Track Minimum Difference

ทำซ้ำสำหรับ num+1 และ num+2 เลือกคู่ที่ Diff น้อยกว่า

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> getDiv(int x) {
        int bestDiff = INT_MAX;
        vector<int> bestPair(2);
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                int a = i, b = x / i;
                int diff = abs(a - b);
                if (diff < bestDiff) {
                    bestDiff = diff;
                    bestPair = {a, b};
                }
            }
        }
        return bestPair;
    }

    vector<int> closestDivisors(int num) {
        auto p1 = getDiv(num + 1);
        auto p2 = getDiv(num + 2);
        return (abs(p1[0] - p1[1]) <= abs(p2[0] - p2[1])) ? p1 : p2;
    }
};

Input / Output

Input:  8
Output: [3, 3]

ความซับซ้อน (Complexity)

• Time: O(√N) — Loop ถึง sqrt(num+2)
• Space: O(1)

จุดสำคัญ

ตัวหารคู่ที่ใกล้ที่สุดจะอยู่ **ใกล้ √x มากที่สุด** ดังนั้น Loop จาก 1 ถึง √x แล้วเก็บคู่สุดท้ายที่เจอ (หรือ Track Min Diff) ก็ได้คำตอบครับ