1.
Introduction to Problem statement
1.1.
Sample Examples
2.
Approach - 1
2.1.
Steps of algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Approach - 2 (Efficient for Q queries)
3.1.
Steps of algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Smallest divisor of N closest to X

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.

Approach - 2 (Efficient for Q queries)

This approach is efficient when we are required to answer Q queries.

Before moving to the approach, let’s learn the lower_bound function:

lower_bound function:

In C++, the lower bound() function returns an iterator pointing to the first element in the range [first, last) with a value greater than or equal to val.
In this approach, we will precompute the divisors of all the numbers from 1 to N by using a modified Sieve of Eratosthenes.
We will use a vector of vectors to store the divisors of all the numbers from 1 to N. Every ith row of this contains all the divisors of the number i.
Now, we can efficiently find the smallest divisor of N closest to X using the binary search algorithm as all the divisors of N in the container is in a sorted manner.
For finding the smallest divisor of N closest to X, we will use the inbuilt lower_bound function in the Nth row.

Must Read Lower Bound in C++

Steps of algorithm

• Create a vector of vectors divs of size MAXM=10000 to store the divisors from 1 to N.
• Precompute the divisor of all the numbers from 1 to N using the modified Sieve of Eratosthenes and store it in divs.
• Find the closest number from X in the Nth row using the lower bound function.
• After using the lower_bound(), if the iterator is pointing to the end of the Nth row. Print the last number of that row.
• Else check the previous number and the pointing number, print the smallest divisor of N closest to X from both of them.

Implementation in C++

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

#define MAXM 100000

vector<vector<int> > divs(MAXM + 1);

void calculateDivisors()
{
for (int i = 1; i <= MAXM; i++)
{
for (int j = i; j <= MAXM; j += i)
{

divs[j].push_back(i);
}
}
}

void closest_divisor(int n, int x)
{
auto it = lower_bound(divs[n].begin(), divs[n].end(), x);

if (it == divs[n].end())
{
it--;
cout << *it << endl;
}
else {
int diff = INT_MAX;

diff = min(diff, abs(*it - x));

if (it != divs[n].begin())
it--;

diff = min(diff, abs(*it - x));

if (n % (x - diff) == 0)
cout << x - diff << endl;
else
cout << x + diff << endl;
}
}

int main()
{
int N = 24;

int Q;
cin >> Q;

calculateDivisors();

while (Q--)
{
int X;
cin >> X;

closest_divisor(N, X);
}

}``````

Input

``````4
20
17
6
9``````

Output

``````24
12
6
8``````

Complexity Analysis

Time complexity: O(max(n*log(logn), Q*logn)), as we are using a modified Sieve of Eratosthenes, where Q is the number of queries we need to answer.

Space complexity: O(MAXM), as we are using a vector of vectors of size MAXM+1, where MAXM is the maximum value of the number N for which we need to find the closest divisor.

FAQs

1. What is Sieve of Eratosthenes C++?
It is used to generate prime numbers within a given range. An integer array with all elements is initialised to zero using this method. Each non-prime element's index is set to 1 for each non-prime element inside the nested loops. The prime numbers are those with a value of 0 in their index.

2. Is Sieve of Eratosthenes dynamic programming?
Yes, we can consider Eratosthenes' Sieve to be an example of dynamic programming. All of the composite numbers will be subproblems.

3. Is binary searching a divide-and-conquer strategy?
Instead of divide-and-conquer, binary search is a decrease-and-conquer algorithm. The Euclidean algorithm for computing the greatest common divisor of two numbers by reducing the numbers to smaller and smaller equivalent subproblems, which dates back several centuries BC, is another ancient decrease-and-conquer algorithm.

4. What is the purpose of the upper_bound function in C++?
upper bound() is a C++ header-defined standard library function. It returns an iterator pointing to the first element greater than the value in the range [first, last], or last if none is found. The elements in the range must be sorted or at the very least partitioned in relation to val.

Key Takeaways

This article discussed the different approaches to finding the Smallest divisor of N closest to X.
First, we discussed the better approach using the property of divisors, i.e. all divisors of a number exist in pairs, and an efficient approach using the modified sieve of Eratosthenes and binary search algorithm with a complete explanation of its implementation in C++.

Check out this problem - Next Smaller Element

If you are an absolute beginner, interested in coding, and want to learn DSA, you can look for our guided path for DSA, which is free!