Count numbers in range [L, R] that are divisible by square root of a number
Given two numbers L and R, the task is to find the count of all numbers in a given range [L, R] that are divisible by the square root of that number. The square root of a number is the value that, when multiplied by itself, gives the original number.
Note: Here square root of a number represents the floor division. i.e, sqrt(4) = 2, sqrt(10) = 3, sqrt(17) = 4.
Examples:
Input: L = 7, R = 18
Output: 5
Explanation: 8, 9, 12, 15, and 16 are divisible by sqrt(num), where num = [L, R]Input: L = 10, R = 15
Output: 2
Explanation: 12, 15 are divisible by sqrt(num), where num = [L, R]
Approach: To solve the problem follow the below idea:
Let x be a square root of a number, Then x can divide at most three numbers in the range [L, R], as shown in example 1: ‘3’ is a square root which divide 9, 12 and 15 only. So, we can use this to find numbers which are divisible by (square root of a number l) + 1 to (square root of a number l) – 1. and then find separately numbers which are divisible by square root of l and r.
Follow the steps to solve the problem:
- First, find numbers that are divisible by the square root of l.
- Then find numbers that are divisible by the square root of r.
- Then find numbers that are divisible by (square root of a number l) + 1 to (square root of a number l) -1. The count of these numbers will be 3*(sqrt(r)-sqrt(l)) because a number can divide at most three elements as shown in example 1
- Then our final answer will be the sum of all these and then return the answer
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 numbers in the range // [L, R] that are divisible by square // root of a number void divisibleNums( int l, int r) { int x, y, ans = 0; // Find next root of // sqrt(l) for checking x = sqrt (l) + 1; // If square root of l and r // is same if (r < x * x) { x = sqrt (l); y = l % x; if (y != 0) { y = x - y; } // Now, l is also divisible // by sqrt(num) if not divisible before l += y; // Finding numbers in the range // from l to r that are divisible // by sqrt(num) ans += ceil ((1.0 * (r - l + 1)) / x); } // If square root of r > sqrt(l) else { // Finding numbers that are // divisible by sqrt(l) ans += ceil ((1.0 * (x * x - 1) - l + 1) / (x - 1)); y = sqrt (r); // Finding numbers that are // divisible by sqrt(r) ans += ceil ((1.0 * (r - (y * y) + 1)) / (y)); // Finding numbers that are // divisible by sqrt(l)+1 // to sqrt(r)-1 ans += (y - x) * 3; // Let x = sqrt(num), x can divide // at most 3 elements in the range // l to r see examples 1 for // better understanding } // Print final answer cout << ans << endl; } // Driver code int main() { int l = 7, r = 18; // Function call for test case 1 divisibleNums(l, r); l = 10; r = 15; // Function call for test case 2 divisibleNums(l, r); return 0; } |
Java
// Java program for the above approach import java.util.*; public class Main { // Function to find numbers in the range // [L, R] that are divisible by square // root of a number public static void divisibleNums( int l, int r) { int x, y, ans = 0 ; // Find next root of // sqrt(l) for checking x = ( int )Math.sqrt(l) + 1 ; // If square root of l and r // is same if (r < x * x) { x = ( int )Math.sqrt(l); y = l % x; if (y != 0 ) { y = x - y; } // Now, l is also divisible // by sqrt(num) if not divisible before l += y; // Finding numbers in the range // from l to r that are divisible // by sqrt(num) ans += Math.ceil(( double )(r - l + 1 ) / x); } // If square root of r > sqrt(l) else { // Finding numbers that are // divisible by sqrt(l) ans += Math.ceil(( double )(x * x - 1 - l + 1 ) / (x - 1 )); y = ( int )Math.sqrt(r); // Finding numbers that are // divisible by sqrt(r) ans += Math.ceil(( double )(r - (y * y) + 1 ) / y); // Finding numbers that are // divisible by sqrt(l)+1 // to sqrt(r)-1 ans += (y - x) * 3 ; // Let x = sqrt(num), x can divide // at most 3 elements in the range // l to r see examples 1 for // better understanding } // Print final answer System.out.println(ans); } public static void main(String[] args) { int l = 7 , r = 18 ; divisibleNums(l, r); l = 10 ; r = 15 ; divisibleNums(l, r); } } |
Python3
# Python program for the above approach import math def divisibleNums(l, r): x, y, ans = 0 , 0 , 0 # Find next root of sqrt(l) for checking x = int (math.sqrt(l)) + 1 # If square root of l and r is same if r < x * x: x = int (math.sqrt(l)) y = l % x if y ! = 0 : y = x - y # Now, l is also divisible by sqrt(num) if not divisible before l + = y # Finding numbers in the range from l to r that are divisible by sqrt(num) ans + = math.ceil((r - l + 1 ) / x) # If square root of r > sqrt(l) else : # Finding numbers that are divisible by sqrt(l) ans + = math.ceil((x * x - 1 - l + 1 ) / (x - 1 )) y = int (math.sqrt(r)) # Finding numbers that are divisible by sqrt(r) ans + = math.ceil((r - (y * y) + 1 ) / y) # Finding numbers that are divisible by sqrt(l)+1 to sqrt(r)-1 ans + = (y - x) * 3 # Let x = sqrt(num), x can divide at most 3 elements # in the range l to r see examples 1 for better understanding # Print final answer print (ans) l = 7 r = 18 divisibleNums(l, r) l = 10 r = 15 divisibleNums(l, r) # This code is contributed by sankar. |
C#
// C# program for the above approach using System; public class GFG { // Function to find numbers in the range [L, R] that are // divisible by square root of a number public static void divisibleNums( int l, int r) { int x, y, ans = 0; // Find next root of sqrt(l) for checking x = ( int )Math.Sqrt(l) + 1; // If square root of l and r is same if (r < x * x) { x = ( int )Math.Sqrt(l); y = l % x; if (y != 0) { y = x - y; } // Now, l is also divisible by sqrt(num) if not // divisible before l += y; // Finding numbers in the range from l to r that // are divisible by sqrt(num) ans += ( int )Math.Ceiling(( double )(r - l + 1) / x); } // If square root of r > sqrt(l) else { // Finding numbers that are divisible by sqrt(l) ans += ( int )Math.Ceiling( ( double )(x * x - 1 - l + 1) / (x - 1)); y = ( int )Math.Sqrt(r); // Finding numbers that are divisible by sqrt(r) ans += ( int )Math.Ceiling( ( double )(r - (y * y) + 1) / y); // Finding numbers that are divisible by // sqrt(l)+1 to sqrt(r)-1 ans += (y - x) * 3; // Let x = sqrt(num), x can divide at most 3 // elements in the range l to r see examples 1 // for better understanding } // Print final answer Console.WriteLine(ans); } static public void Main() { // Code int l = 7, r = 18; divisibleNums(l, r); l = 10; r = 15; divisibleNums(l, r); } } // This code is contributed by karthik. |
Javascript
// JavaScript program for the above approach function divisibleNums(l, r) { let x, y, ans = 0; // Find next root of sqrt(l) for checking x = Math.sqrt(l) + 1 | 0; // If square root of l and r is same if (r < x * x) { x = Math.sqrt(l) | 0; y = l % x; if (y != 0) { y = x - y; } // Now, l is also divisible by sqrt(num) if not // divisible before l += y; // Finding numbers in the range from l to r that // are divisible by sqrt(num) ans += Math.ceil((r - l + 1) / x); } // If square root of r > sqrt(l) else { // Finding numbers that are divisible by sqrt(l) ans += Math.ceil((x * x - 1 - l + 1) / (x - 1)); y = Math.sqrt(r) | 0; // Finding numbers that are divisible by sqrt(r) ans += Math.ceil((r - (y * y) + 1) / y); // Finding numbers that are divisible by // sqrt(l)+1 to sqrt(r)-1 ans += (y - x) * 3; // Let x = sqrt(num), x can divide at most 3 // elements in the range l to r see examples // 1 for better understanding } // Print final answer console.log(ans + "<br>" ); } var l = 7, r = 18 divisibleNums(l, r); l = 10 r = 15 divisibleNums(l, r); // This code is contributed by sankar. |
5 2
Time Complexity: O(1)
Auxiliary Space: O(1)