Count numbers in range [L, R] that are divisible by square root of a number

By Ann Roberts On Feb 14, 2023

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

#include <bits/stdc++.h>

using namespace std;

void divisibleNums(int l, int r)

{

int x, y, ans = 0;

x = sqrt(l) + 1;

if (r < x * x) {

x = sqrt(l);

y = l % x;

if (y != 0) {

y = x - y;

}

l += y;

ans += ceil((1.0 * (r - l + 1)) / x);

}

else {

ans += ceil((1.0 * (x * x - 1) - l + 1) / (x - 1));

y = sqrt(r);

ans += ceil((1.0 * (r - (y * y) + 1)) / (y));

ans += (y - x) * 3;

}

cout << ans << endl;

}

int main()

{

int l = 7, r = 18;

divisibleNums(l, r);

l = 10;

r = 15;

divisibleNums(l, r);

return 0;

}

Time Complexity: O(1)
Auxiliary Space: O(1)

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

#include <bits/stdc++.h>

using namespace std;

void divisibleNums(int l, int r)

{

int x, y, ans = 0;

x = sqrt(l) + 1;

if (r < x * x) {

x = sqrt(l);

y = l % x;

if (y != 0) {

y = x - y;

}

l += y;

ans += ceil((1.0 * (r - l + 1)) / x);

}

else {

ans += ceil((1.0 * (x * x - 1) - l + 1) / (x - 1));

y = sqrt(r);

ans += ceil((1.0 * (r - (y * y) + 1)) / (y));

ans += (y - x) * 3;

}

cout << ans << endl;

}

int main()

{

int l = 7, r = 18;

divisibleNums(l, r);

l = 10;

r = 15;

divisibleNums(l, r);

return 0;

}

Time Complexity: O(1)
Auxiliary Space: O(1)

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.