Count elements in the given range which have maximum number of divisors - Coding

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++

<?php 
// PHP implementation of above approach
 
// Function to count the divisors
function 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 divisors
function 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 call
echo MaximumDivisors($X, $Y)." ";
 
// This code is contributed
// by ChitraNayal
?>

Javascript

<?php 
// PHP implementation of above approach
 
// Function to count the elements
// with maximum number of divisors
function 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 divisors
function 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 code
let X = 1, Y = 10;
 
document.write(MaximumDivisors(X, Y));
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output:

Time Complexity : O((Y – X + 1) * sqrt(Y))
Space Complexity : O(Y – X + 1)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Elements that occurred only once in the array
Longest subarray having average greater than or equal to x \| Set-2
Sorting a dynamic 2-dimensional array of Strings
Find the largest area rectangular sub-matrix whose sum is equal to k
Sort a nearly sorted array using STL

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	7