## Introduction to Problem statement

We are given a number N and a number X. Our task is to find the smallest divisor of N closest to X, i.e. the difference between the divisor of N and X is minimum.

### Sample Examples

**Example 1:**

```
Input: N = 25, X = 6
Output: 5
Explanation
Divisors of 25 are: (1, 5, 25)
The smallest divisor of 25 closest to 6 = 5
```

**Example 2:**

```
Input: N= 24, X = 16
Output: 12
Explanation
Divisors of 24 are: (1, 2, 3, 4, 6, 8, 12, 24)
The smallest divisor of 24 closest to 16 = 12
```

Also see, __Euclid GCD Algorithm__

## Approach - 1

The idea is simple, traverse through all the divisors of N and find the divisor closest to X.

For traversing through all the divisors of N, if we observe carefully, all the number's divisors exist in pairs. For example, if N = 24, the divisors are (1, 24), (2, 12), (3, 8), (4, 6).

All the divisors of N are in the form of (i, N/i)

Using this important observation, we can significantly speed up our program.

### Steps of algorithm

- Create a closest_div variable and initialise it with -1.
- Create a diff variable and initialise it with INT_MAX.
- Run a loop for sqrt(N) times as divisors of a number are present in pairs.
- If N is divisible by current number i,
- Check the first divisor of N (i) in the pair; it is the current closest number to X or not. If yes, update the value of diff and closest_div.
- Similarly, check for the second divisor of N (N/i) in the pair and update the diff and closest_div.
- Finally, print the value of closest_div.

Below is the implementation of the above approach:

### Implementation in C++

```
#include <bits/stdc++.h>
using namespace std;
int find_Closest(int N, int x)
{
int closest_div = -1;
int diff = INT_MAX;
for (int i = 1; i * i <= N; i++)
{
if (N % i == 0)
{
if (abs(x - i) < diff)
{
diff = abs(x - i);
closest_div = i;
}
if (abs(x - N / i) < diff)
{
diff = abs(x - N / i);
closest_div = N / i;
}
}
}
cout << closest_div;
}
int main()
{
int N = 24, X = 16;
find_Closest(N, X);
return 0;
}
```

**Output**

`12`

#### Complexity Analysis

**Time complexity:** O(sqrt(N)), as we are running a loop of size sqrt(N), where N is the given number.

**Space complexity:** O(1), as we are using constant extra space.