Count elements in the given range which have maximum number of divisors
Given two numbers X and Y. The task is to find the number of elements in the range [X,Y] both inclusive, that have the maximum number of divisors.
Examples:
Input: X = 2, Y = 9
Output: 2
6, 8 are numbers with the maximum number of divisors.Input: X = 1, Y = 10
Output: 3
6, 8, 10 are numbers with the maximum number of divisors.
Method 1:
- Traverse all the elements from X to Y one by one.
- Find the number of divisors of each element.
- Store the number of divisors in an array and update the maximum number of Divisors(maxDivisors).
- Traverse the array that contains divisors and counts the number of elements equal to maxDivisors.
- Return the count.
Below is the implementation of above method:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to count the divisorsint countDivisors(int n){ int count = 0; // Note that this loop runs till square root for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, print only one if (n / i == i) count++; else // Otherwise print both count += 2; } } return count;}// Function to count the number with// maximum divisorsint MaximumDivisors(int X, int Y){ int maxDivisors = INT_MIN, result = 0; // to store number of divisors int arr[Y - X + 1]; // Traverse from X to Y for (int i = X; i <= Y; i++) { // Count the number of divisors of i int Div = countDivisors(i); // Store the value of div in an array arr[i - X] = Div; // Update the value of maxDivisors maxDivisors = max(Div, maxDivisors); } // Traverse the array for (int i = 0; i < (Y - X + 1); i++) // Count the value equals to maxDivisors if (arr[i] == maxDivisors) result++; return result;}// Driver Codeint main(){ int X = 1, Y = 10; // function call cout << MaximumDivisors(X, Y) << endl; return 0;} |
C
// C implementation of above approach#include <stdio.h>#include <math.h>#include <limits.h>int max(int a,int b){ int max = a; if(max < b) max = b; return max;}// Function to count the divisorsint countDivisors(int n){ int count = 0; // Note that this loop runs till square root for (int i = 1; i <= sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, print only one if (n / i == i) count++; else // Otherwise print both count += 2; } } return count;}// Function to count the number with// maximum divisorsint MaximumDivisors(int X, int Y){ int maxDivisors = INT_MIN, result = 0; // to store number of divisors int arr[Y - X + 1]; // Traverse from X to Y for (int i = X; i <= Y; i++) { // Count the number of divisors of i int Div = countDivisors(i); // Store the value of div in an array arr[i - X] = Div; // Update the value of maxDivisors maxDivisors = max(Div, maxDivisors); } // Traverse the array for (int i = 0; i < (Y - X + 1); i++) // Count the value equals to maxDivisors if (arr[i] == maxDivisors) result++; return result;}// Driver Codeint main(){ int X = 1, Y = 10; // function call printf("%d\n",MaximumDivisors(X, Y)); return 0;}// This code is contributed by kothavvsaakash. |
Java
// Java implementation of above approachclass GFG {// Function to count the divisorsstatic int countDivisors(int n){int count = 0;// Note that this loop // runs till square rootfor (int i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // print only one if (n / i == i) count++; else // Otherwise print both count += 2; }}return count;}// Function to count the number // with maximum divisorsstatic int MaximumDivisors(int X, int Y){int maxDivisors = 0, result = 0;// to store number of divisorsint[] arr = new int[Y - X + 1];// Traverse from X to Yfor (int i = X; i <= Y; i++) { // Count the number of divisors of i int Div = countDivisors(i); // Store the value of div in an array arr[i - X] = Div; // Update the value of maxDivisors maxDivisors = Math.max(Div, maxDivisors);}// Traverse the array for (int i = 0; i < (Y - X + 1); i++) // Count the value equals // to maxDivisors if (arr[i] == maxDivisors) result++;return result;}// Driver Codepublic static void main(String[] args) { int X = 1, Y = 10; // function call System.out.println(MaximumDivisors(X, Y));}}// This code is contributed // by ChitraNayal |
Python3
# from math module import everythingfrom math import *# Python 3 implementation of above approach# Function to count the divisors def countDivisors(n) : count = 0 # Note that this loop runs till square root for i in range(1,int(sqrt(n)+1)) : if n % i == 0 : # If divisors are equal, print only one if n / i == i : count += 1 # Otherwise print both else : count += 2 return count# Function to count the number with # maximum divisors def MaximumDivisors(X,Y) : result = 0 maxDivisors = 0 # create list to store number of divisors arr = [] # initialize with 0 upto length Y-X+1 for i in range(Y - X + 1) : arr.append(0) # Traverse from X to Y for i in range(X,Y+1) : # Count the number of divisors of i Div = countDivisors(i) # Store the value of div in an array arr[i - X] = Div # Update the value of maxDivisors maxDivisors = max(Div,maxDivisors) # Traverse the array for i in range (Y - X + 1) : # Count the value equals to maxDivisors if arr[i] == maxDivisors : result += 1 return result# Driver codeif __name__ == "__main__" : X, Y = 1, 10 # function call print(MaximumDivisors(X,Y)) |
C#
// C# implementation of above approachusing System;class GFG{// Function to count the divisorsstatic int countDivisors(int n){int count = 0;// Note that this loop // runs till square rootfor (int i = 1; i <= Math.Sqrt(n); i++){ if (n % i == 0) { // If divisors are equal, // print only one if (n / i == i) count++; else // Otherwise print both count += 2; }}return count;}// Function to count the number // with maximum divisorsstatic int MaximumDivisors(int X, int Y){int maxDivisors = 0, result = 0;// to store number of divisorsint[] arr = new int[Y - X + 1];// Traverse from X to Yfor (int i = X; i <= Y; i++){ // Count the number of divisors of i int Div = countDivisors(i); // Store the value of div in an array arr[i - X] = Div; // Update the value of maxDivisors maxDivisors = Math.Max(Div, maxDivisors);}// Traverse the array for (int i = 0; i < (Y - X + 1); i++) // Count the value equals // to maxDivisors if (arr[i] == maxDivisors) result++;return result;}// Driver Codepublic static void Main(){ int X = 1, Y = 10; // function call Console.Write(MaximumDivisors(X, Y));}}// This code is contributed// by ChitraNayal |
PHP
<?php // PHP implementation of above approach// Function to count the divisorsfunction countDivisors($n){ $count = 0; // Note that this loop // runs till square root for ($i = 1; $i <= sqrt($n); $i++) { if ($n % $i == 0) { // If divisors are equal, // print only one if ($n / $i == $i) $count++; else // Otherwise print both $count += 2; } } return $count;}// Function to count the number // with maximum divisorsfunction MaximumDivisors($X, $Y){ $maxDivisors = PHP_INT_MIN; $result = 0; // to store number of divisors $arr = array_fill(0, ($Y - $X + 1), NULL); // Traverse from X to Y for ($i = $X; $i <= $Y; $i++) { // Count the number of divisors of i $Div = countDivisors($i); // Store the value of div in an array $arr[$i - $X] = $Div; // Update the value of maxDivisors $maxDivisors = max($Div, $maxDivisors); } // Traverse the array for ($i = 0; $i < ($Y - $X + 1); $i++) // Count the value equals to maxDivisors if ($arr[$i] == $maxDivisors) $result++; return $result;}// Driver Code$X = 1;$Y = 10;// function callecho MaximumDivisors($X, $Y)." ";// This code is contributed// by ChitraNayal?> |
Javascript
<script>// Javascript implementation of above approach// Function to count the divisorsfunction countDivisors(n){ let count = 0; // Note that this loop // runs till square root for(let i = 1; i <= Math.sqrt(n); i++) { if (n % i == 0) { // If divisors are equal, // print only one if (Math.floor(n / i) == i) count++; else // Otherwise print both count += 2; } } return count;}// Function to count the number // with maximum divisorsfunction MaximumDivisors(X, Y){ let maxDivisors = 0, result = 0; // To store number of divisors let arr = new Array(Y - X + 1); // Traverse from X to Y for(let i = X; i <= Y; i++) { // Count the number of divisors of i let Div = countDivisors(i); // Store the value of div in an array arr[i - X] = Div; // Update the value of maxDivisors maxDivisors = Math.max(Div, maxDivisors); } // Traverse the array for(let i = 0; i < (Y - X + 1); i++) // Count the value equals // to maxDivisors if (arr[i] == maxDivisors) result++; return result;}// Driver Codelet X = 1, Y = 10;// Function calldocument.write(MaximumDivisors(X, Y));// This code is contributed by rag2127</script> |
Output:
3
Time Complexity: O(sqrt(n))
Auxiliary Space: O(n)
Method 2:
- Create an array of size Y-X+1 to store number of divisors of X in arr[0], X+1 in arr[1]… up to Y.
- To get the number of divisors of all numbers from X to Y run two loops(nested).
- Run an outer loop from 1 to sqrt(Y).
- Run an inner loop from first_divisible to Y.
- First_divisible is the number which is the first number to be divisible by I(outer loop) and greater than or equals to X.
Here, first_divisible is calculated by using Find the number closest to n and divisible by m method. Then find divisors of the number.
Below is the implementation of above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to count the elements// with maximum number of divisorsint MaximumDivisors(int X, int Y){ // to store number of divisors int arr[Y - X + 1]; // initialise with zero memset(arr, 0, sizeof(arr)); // to store the maximum number of divisors int mx = INT_MIN; // to store required answer int cnt = 0; for (int i = 1; i * i <= Y; i++) { int sq = i * i; int first_divisible; // Find the first divisible number if ((X / i) * i >= X) first_divisible = (X / i) * i; else first_divisible = (X / i + 1) * i; // Count number of divisors for (int j = first_divisible; j <= Y; j += i) { if (j < sq) continue; else if (j == sq) arr[j - X]++; else arr[j - X] += 2; } } // Find number of elements with // maximum number of divisors for (int i = X; i <= Y; i++) { if (arr[i - X] > mx) { cnt = 1; mx = arr[i - X]; } else if (arr[i - X] == mx) cnt++; } return cnt;}// Driver codeint main(){ int X = 1, Y = 10; cout << MaximumDivisors(X, Y) << endl; return 0;} |
C
// C implementation of above approach#include <stdio.h>#include <limits.h>#include <string.h>// Function to count the elements// with maximum number of divisorsint MaximumDivisors(int X, int Y){ // to store number of divisors int arr[Y - X + 1]; // initialise with zero memset(arr, 0, sizeof(arr)); // to store the maximum number of divisors int mx = INT_MIN; // to store required answer int cnt = 0; for (int i = 1; i * i <= Y; i++) { int sq = i * i; int first_divisible; // Find the first divisible number if ((X / i) * i >= X) first_divisible = (X / i) * i; else first_divisible = (X / i + 1) * i; // Count number of divisors for (int j = first_divisible; j <= Y; j += i) { if (j < sq) continue; else if (j == sq) arr[j - X]++; else arr[j - X] += 2; } } // Find number of elements with // maximum number of divisors for (int i = X; i <= Y; i++) { if (arr[i - X] > mx) { cnt = 1; mx = arr[i - X]; } else if (arr[i - X] == mx) cnt++; } return cnt;}// Driver codeint main(){ int X = 1, Y = 10; printf("%d\n",MaximumDivisors(X, Y)); return 0;}// This code is contributed by kothavvsaakash. |
Java
// Java implementation of above approachclass GFG {// Function to count the elements// with maximum number of divisorsstatic int MaximumDivisors(int X, int Y){ // to store number of divisorsint[] arr = new int[Y - X + 1];// initialise with zerofor(int i = 0; i < arr.length; i++) arr[i] = 0;// to store the maximum // number of divisorsint mx = 0;// to store required answerint cnt = 0;for (int i = 1; i * i <= Y; i++){ int sq = i * i; int first_divisible; // Find the first divisible number if ((X / i) * i >= X) first_divisible = (X / i) * i; else first_divisible = (X / i + 1) * i; // Count number of divisors for (int j = first_divisible; j <= Y; j += i) { if (j < sq) continue; else if (j == sq) arr[j - X]++; else arr[j - X] += 2; }}// Find number of elements with// maximum number of divisorsfor (int i = X; i <= Y; i++){ if (arr[i - X] > mx) { cnt = 1; mx = arr[i - X]; } else if (arr[i - X] == mx) cnt++;}return cnt;}// Driver codepublic static void main(String[] args) { int X = 1, Y = 10; System.out.println(MaximumDivisors(X, Y));}}// This code is contributed // by ChitraNayal |
Python3
# Python 3 implementation of above approach# Function to count the elements# with maximum number of divisorsdef MaximumDivisors(X, Y): # to store number of divisors # initialise with zero arr = [0] * (Y - X + 1) # to store the maximum # number of divisors mx = 0 # to store required answer cnt = 0 i = 1 while i * i <= Y : sq = i * i # Find the first divisible number if ((X // i) * i >= X) : first_divisible = (X // i) * i else: first_divisible = (X // i + 1) * i # Count number of divisors for j in range(first_divisible, Y + 1, i): if j < sq : continue elif j == sq : arr[j - X] += 1 else: arr[j - X] += 2 i += 1 # Find number of elements with # maximum number of divisors for i in range(X, Y + 1): if arr[i - X] > mx : cnt = 1 mx = arr[i - X] elif arr[i - X] == mx : cnt += 1 return cnt# Driver codeif __name__ == "__main__": X = 1 Y = 10 print(MaximumDivisors(X, Y))# This code is contributed # by ChitraNayal |
C#
// C# implementation of above approachusing System;class GFG {// Function to count the elements// with maximum number of divisorsstatic int MaximumDivisors(int X, int Y){ // to store number of divisorsint[] arr = new int[Y - X + 1];// initialise with zerofor(int i = 0; i < arr.Length; i++) arr[i] = 0;// to store the maximum // number of divisorsint mx = 0;// to store required answerint cnt = 0;for (int i = 1; i * i <= Y; i++) { int sq = i * i; int first_divisible; // Find the first divisible number if ((X / i) * i >= X) first_divisible = (X / i) * i; else first_divisible = (X / i + 1) * i; // Count number of divisors for (int j = first_divisible; j <= Y; j += i) { if (j < sq) continue; else if (j == sq) arr[j - X]++; else arr[j - X] += 2; }}// Find number of elements with// maximum number of divisorsfor (int i = X; i <= Y; i++){ if (arr[i - X] > mx) { cnt = 1; mx = arr[i - X]; } else if (arr[i - X] == mx) cnt++;}return cnt;}// Driver codepublic static void Main(){ int X = 1, Y = 10; Console.Write(MaximumDivisors(X, Y));}}// This code is contributed // by ChitraNayal |
PHP
<?php // PHP implementation of above approach// Function to count the elements// with maximum number of divisorsfunction MaximumDivisors($X, $Y){ // to store number of divisors // initialise with zero $arr = array_fill(0,($Y - $X + 1), NULL); // to store the maximum // number of divisors $mx = PHP_INT_MIN; // to store required answer $cnt = 0; for ($i = 1; $i * $i <= $Y; $i++) { $sq = $i * $i; // Find the first divisible number if (($X / $i) * $i >= $X) $first_divisible = ($X / $i) * $i; else $first_divisible = ($X / $i + 1) * $i; // Count number of divisors for ($j = $first_divisible; $j < $Y; $j += $i) { if ($j < $sq) continue; else if ($j == $sq) $arr[$j - $X]++; else $arr[$j - $X] += 2; } } // Find number of elements with // maximum number of divisors for ($i = $X; $i <= $Y; $i++) { if ($arr[$i - $X] > $mx) { $cnt = 1; $mx = $arr[$i - $X]; } else if ($arr[$i - $X] == $mx) $cnt++; } return $cnt;}// Driver code$X = 1;$Y = 10;echo MaximumDivisors($X, $Y)."\n";// This code is contributed // by ChitraNayal?> |
Javascript
<script>// Javascript implementation of above approach// Function to count the elements// with maximum number of divisorsfunction MaximumDivisors(X, Y){ // To store number of divisors let arr = new Array(Y - X + 1); // Initialise with zero for(let i = 0; i < arr.length; i++) arr[i] = 0; // To store the maximum // number of divisors let mx = 0; // To store required answer let cnt = 0; for(let i = 1; i * i <= Y; i++) { let sq = i * i; let first_divisible; // Find the first divisible number if (Math.floor(X / i) * i >= X) first_divisible = Math.floor(X / i) * i; else first_divisible = (Math.floor(X / i) + 1) * i; // Count number of divisors for(let j = first_divisible; j <= Y; j += i) { if (j < sq) continue; else if (j == sq) arr[j - X]++; else arr[j - X] += 2; } } // Find number of elements with // maximum number of divisors for(let i = X; i <= Y; i++) { if (arr[i - X] > mx) { cnt = 1; mx = arr[i - X]; } else if (arr[i - X] == mx) cnt++; } return cnt;}// Driver codelet X = 1, Y = 10;document.write(MaximumDivisors(X, Y));// This code is contributed by avanitrachhadiya2155</script> |
Output:
3
Time Complexity : O((Y – X + 1) * sqrt(Y))
Space Complexity : O(Y – X + 1)
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!
