Smallest divisor of N closest to X
Given two positive integers N and X, the task is to find the smallest divisor of N which is closest to X.
Examples:
Input: N = 16, X = 5
Output: 4
Explanation:
4 is the divisor of 16 which is closest to 5.Input: N = 27, X = 15
Output: 9
Explanation:
9 is the divisor of 27 closest to 15.
Naive Approach: The simplest approach to solve the problem is to iterate through all the values up to N and find the closest one to X that divides N.
Time Complexity: O(N)
Auxiliary Space: O(1)
Better Approach: A better idea is to iterate through all the divisors of N and check for the divisor closest to X.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the divisor of N// closest to the targetint findClosest(int N, int target){ int closest = -1; int diff = INT_MAX; // Iterate till square root of N for (int i = 1; i <= sqrt(N); i++) { if (N % i == 0) { // Check if divisors are equal if (N / i == i) { // Check if i is the closest if (abs(target - i) < diff) { diff = abs(target - i); closest = i; } } else { // Check if i is the closest if (abs(target - i) < diff) { diff = abs(target - i); closest = i; } // Check if n / i is the closest if (abs(target - N / i) < diff) { diff = abs(target - N / i); closest = N / i; } } } } // Print the closest value cout << closest;}// Driver Codeint main(){ // Given N & X int N = 16, X = 5; // Function Call findClosest(N, X); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG { // Function to find the divisor of N // closest to the target static void findClosest(int N, int target) { int closest = -1; int diff = Integer.MAX_VALUE; // Iterate till square root of N for (int i = 1; i <= (int)Math.sqrt(N); i++) { if (N % i == 0) { // Check if divisors are equal if (N / i == i) { // Check if i is the closest if (Math.abs(target - i) < diff) { diff = Math.abs(target - i); closest = i; } } else { // Check if i is the closest if (Math.abs(target - i) < diff) { diff = Math.abs(target - i); closest = i; } // Check if n / i is the closest if (Math.abs(target - N / i) < diff) { diff = Math.abs(target - N / i); closest = N / i; } } } } // Print the closest value System.out.println(closest); } // Driver code public static void main(String[] args) { // Given N & X int N = 16, X = 5; // Function Call findClosest(N, X); }}// This code is contributed by code_hunt. |
Python3
# Python3 program for the above approachfrom math import sqrt, floor, ceil# Function to find the divisor of N# closest to the targetdef findClosest(N, target): closest = -1 diff = 10**18 # Iterate till square root of N for i in range(1, ceil(sqrt(N)) + 1): if (N % i == 0): # Check if divisors are equal if (N // i == i): # Check if i is the closest if (abs(target - i) < diff): diff = abs(target - i) closest = i else: # Check if i is the closest if (abs(target - i) < diff): diff = abs(target - i) closest = i # Check if n / i is the closest if (abs(target - N // i) < diff): diff = abs(target - N // i) closest = N // i # Print the closest value print(closest)# Driver Codeif __name__ == '__main__': # Given N & X N, X = 16, 5 # Function Call findClosest(N, X) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG { // Function to find the divisor of N // closest to the target static void findClosest(int N, int target) { int closest = -1; int diff = Int32.MaxValue; // Iterate till square root of N for (int i = 1; i <= Math.Sqrt(N); i++) { if (N % i == 0) { // Check if divisors are equal if (N / i == i) { // Check if i is the closest if (Math.Abs(target - i) < diff) { diff = Math.Abs(target - i); closest = i; } } else { // Check if i is the closest if (Math.Abs(target - i) < diff) { diff = Math.Abs(target - i); closest = i; } // Check if n / i is the closest if (Math.Abs(target - N / i) < diff) { diff = Math.Abs(target - N / i); closest = N / i; } } } } // Print the closest value Console.Write(closest); } // Driver code static void Main() { // Given N & X int N = 16, X = 5; // Function Call findClosest(N, X); }}// This code is contributed by divyeshrabadiya07 |
Javascript
<script>// Javascript program for the above approach// Function to find the divisor of N// closest to the targetfunction findClosest(N, target){ let closest = -1; let diff = Number.MAX_VALUE; // Iterate till square root of N for (let i = 1; i <= Math.sqrt(N); i++) { if (N % i == 0) { // Check if divisors are equal if (N / i == i) { // Check if i is the closest if (Math.abs(target - i) < diff) { diff = Math.abs(target - i); closest = i; } } else { // Check if i is the closest if (Math.abs(target - i) < diff) { diff = Math.abs(target - i); closest = i; } // Check if n / i is the closest if (Math.abs(target - N / i) < diff) { diff = Math.abs(target - N / i); closest = N / i; } } } } // Print the closest value document.write(closest);}// driver function // Given N & X let N = 16, X = 5; // Function Call findClosest(N, X); // This code is contributed by souravghosh0416.</script> |
Output:
4
Time Complexity: O(sqrt(N))
Auxiliary Space: O(1)
Efficient Approach: The optimal idea is to pre-compute the divisors of all the numbers from 1 to N using a modified form of Sieve Of Eratosthenes and then use Binary Search to find the closest value to the given target.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Define macros#define MAX 10000vector<vector<int> > divisors(MAX + 1);// Stores divisors for all numbers// in the vector divisorsvoid computeDivisors(){ for (int i = 1; i <= MAX; i++) { for (int j = i; j <= MAX; j += i) { // i is the divisor and // j is the multiple divisors[j].push_back(i); } }}// Function to compare the closeness of the given// targetint getClosest(int val1, int val2, int target){ if (target - val1 >= val2 - target) return val2; else return val1;}// Function to find the element closest to// target in divisors vectorint findClosest(vector<int>& arr, int n, int target){ // Corner cases if (target <= arr[0]) return arr[0]; if (target >= arr[n - 1]) return arr[n - 1]; // Perform binary search int i = 0, j = n, mid = 0; while (i < j) { mid = (i + j) / 2; if (arr[mid] == target) return arr[mid]; // Check if target is less than the array // element then search in left half if (target < arr[mid]) { // Check if target is greater // than previous // to mid, return closest of two if (mid > 0 && target > arr[mid - 1]) return getClosest(arr[mid - 1], arr[mid], target); // Repeat for left half j = mid; } // Check if target is greater than mid else { if (mid < n - 1 && target < arr[mid + 1]) return getClosest(arr[mid], arr[mid + 1], target); // Update i i = mid + 1; } } // Only single element left after search return arr[mid];}// Function to print the divisor of N closest to Xvoid printClosest(int N, int X){ // Function call to calculate and stores // divisors of all numbers in a vector computeDivisors(); // Stores the closest value to target int ans = findClosest(divisors[N], divisors[N].size(), X); // Print the answer cout << ans;}// Driver Codeint main(){ // Given N & X int N = 16, X = 5; // Function Call printClosest(N, X);} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Define macrosstatic final int MAX = 10000;static Vector<Integer>[] divisors = new Vector[MAX + 1];// Stores divisors for all numbers// in the vector divisorsstatic void computeDivisors(){ for (int i = 1; i <= MAX; i++) { for (int j = i; j <= MAX; j += i) { // i is the divisor and // j is the multiple divisors[j].add(i); } }}// Function to compare the closeness of the given// targetstatic int getClosest(int val1, int val2, int target){ if (target - val1 >= val2 - target) return val2; else return val1;}// Function to find the element closest to// target in divisors vectorstatic int findClosest(Vector<Integer> array, int n, int target){ Integer []arr = array.toArray(new Integer[array.size()]); // Corner cases if (target <= arr[0]) return arr[0]; if (target >= arr[n - 1]) return arr[n - 1]; // Perform binary search int i = 0, j = n, mid = 0; while (i < j) { mid = (i + j) / 2; if (arr[mid] == target) return arr[mid]; // Check if target is less than the array // element then search in left half if (target < arr[mid]) { // Check if target is greater // than previous // to mid, return closest of two if (mid > 0 && target > arr[mid - 1]) return getClosest(arr[mid - 1], arr[mid], target); // Repeat for left half j = mid; } // Check if target is greater than mid else { if (mid < n - 1 && target < arr[mid + 1]) return getClosest(arr[mid], arr[mid + 1], target); // Update i i = mid + 1; } } // Only single element left after search return arr[mid];}// Function to print the divisor of N closest to Xstatic void printClosest(int N, int X){ // Function call to calculate and stores // divisors of all numbers in a vector computeDivisors(); // Stores the closest value to target int ans = findClosest(divisors[N], divisors[N].size(), X); // Print the answer System.out.print(ans);}// Driver Codepublic static void main(String[] args){ // Given N & X int N = 16, X = 5; for(int i = 0; i < divisors.length; i++) divisors[i] = new Vector<Integer>(); // Function Call printClosest(N, X);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program for the above approachMAX = 10000divisors = [[] for i in range(MAX + 1)]# Stores divisors for all numbers# in the vector divisorsdef computeDivisors(): global divisors global MAX for i in range(1, MAX + 1, 1): for j in range(i, MAX + 1, i): # i is the divisor and # j is the multiple divisors[j].append(i)# Function to compare the closeness of the given# targetdef getClosest(val1, val2, target): if (target - val1 >= val2 - target): return val2 else: return val1# Function to find the element closest to# target in divisors vectordef findClosest(arr, n, target): # Corner cases if (target <= arr[0]): return arr[0] if (target >= arr[n - 1]): return arr[n - 1] # Perform binary search i = 0 j = n mid = 0 while (i < j): mid = (i + j) // 2 if (arr[mid] == target): return arr[mid] # Check if target is less than the array # element then search in left half if (target < arr[mid]): # Check if target is greater # than previous # to mid, return closest of two if (mid > 0 and target > arr[mid - 1]): return getClosest(arr[mid - 1], arr[mid],target) # Repeat for left half j = mid # Check if target is greater than mid else: if (mid < n - 1 and target < arr[mid + 1]): return getClosest(arr[mid], arr[mid + 1], target) # Update i i = mid + 1 # Only single element left after search return arr[mid]# Function to print the divisor of N closest to Xdef printClosest(N, X): global divisors # Function call to calculate and stores # divisors of all numbers in a vector computeDivisors() # Stores the closest value to target ans = findClosest(divisors[N], len(divisors[N]), X) # Print the answer print(ans)# Driver Codeif __name__ == '__main__': # Given N & X N = 16 X = 5 # Function Call printClosest(N, X) # This code is contributed by SURENDRA_GANGWAR |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Define macrosstatic readonly int MAX = 10000;static List<int>[] divisors = new List<int>[MAX + 1];// Stores divisors for all numbers// in the vector divisorsstatic void computeDivisors(){ for (int i = 1; i <= MAX; i++) { for (int j = i; j <= MAX; j += i) { // i is the divisor and // j is the multiple divisors[j].Add(i); } }}// Function to compare the closeness of the given// targetstatic int getClosest(int val1, int val2, int target){ if (target - val1 >= val2 - target) return val2; else return val1;}// Function to find the element closest to// target in divisors vectorstatic int findClosest(List<int> array, int n, int target){ int []arr = array.ToArray(); // Corner cases if (target <= arr[0]) return arr[0]; if (target >= arr[n - 1]) return arr[n - 1]; // Perform binary search int i = 0, j = n, mid = 0; while (i < j) { mid = (i + j) / 2; if (arr[mid] == target) return arr[mid]; // Check if target is less than the array // element then search in left half if (target < arr[mid]) { // Check if target is greater // than previous // to mid, return closest of two if (mid > 0 && target > arr[mid - 1]) return getClosest(arr[mid - 1], arr[mid], target); // Repeat for left half j = mid; } // Check if target is greater than mid else { if (mid < n - 1 && target < arr[mid + 1]) return getClosest(arr[mid], arr[mid + 1], target); // Update i i = mid + 1; } } // Only single element left after search return arr[mid];}// Function to print the divisor of N closest to Xstatic void printClosest(int N, int X){ // Function call to calculate and stores // divisors of all numbers in a vector computeDivisors(); // Stores the closest value to target int ans = findClosest(divisors[N], divisors[N].Count, X); // Print the answer Console.Write(ans);}// Driver Codepublic static void Main(String[] args){ // Given N & X int N = 16, X = 5; for(int i = 0; i < divisors.Length; i++) divisors[i] = new List<int>(); // Function Call printClosest(N, X);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program for the above approach// Define macroslet MAX = 10000;let divisors = new Array(MAX + 1);// Stores divisors for all numbers// in the vector divisorsfunction computeDivisors(){ for(let i = 1; i <= MAX; i++) { for(let j = i; j <= MAX; j += i) { // i is the divisor and // j is the multiple divisors[j].push(i); } }}// Function to compare the closeness of the given// targetfunction getClosest(val1, val2, target){ if (target - val1 >= val2 - target) return val2; else return val1;}// Function to find the element closest to// target in divisors vectorfunction findClosest(arr, n, target){ // Corner cases if (target <= arr[0]) return arr[0]; if (target >= arr[n - 1]) return arr[n - 1]; // Perform binary search let i = 0, j = n, mid = 0; while (i < j) { mid = Math.floor((i + j) / 2); if (arr[mid] == target) return arr[mid]; // Check if target is less than the array // element then search in left half if (target < arr[mid]) { // Check if target is greater // than previous // to mid, return closest of two if (mid > 0 && target > arr[mid - 1]) return getClosest(arr[mid - 1], arr[mid], target); // Repeat for left half j = mid; } // Check if target is greater than mid else { if (mid < n - 1 && target < arr[mid + 1]) return getClosest(arr[mid], arr[mid + 1], target); // Update i i = mid + 1; } } // Only single element left after search return arr[mid];}// Function to print the divisor of N closest to Xfunction printClosest(N, X){ // Function call to calculate and stores // divisors of all numbers in a vector computeDivisors(); // Stores the closest value to target let ans = findClosest(divisors[N], divisors[N].length, X); // Print the answer document.write(ans);}// Driver Code// Given N & Xlet N = 16, X = 5;for(let i = 0; i < divisors.length; i++) divisors[i] = [];// Function CallprintClosest(N, X);// This code is contributed by unknown2108</script> |
Output:
4
Time Complexity: O(N*log(log(N)))
Auxiliary Space: O(MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
