Number of elements with odd factors in given range - GeeksforGeeks
Given a range [n,m], find the number of elements that have odd number of factors in the given range (n and m inclusive).
Read full article from Number of elements with odd factors in given range - GeeksforGeeks
Given a range [n,m], find the number of elements that have odd number of factors in the given range (n and m inclusive).
An Efficient Solution is to observe the pattern. Only those numbers, which are perfect Squares have an odd number of factors.
The answer is difference between square root of m and n-1 (not n)
There is a little caveat. As both n and m are inclusive, if n is a perfect square, we will get an answer which is less than one the actual answer. To understand this, consider range [4, 36]. Answer is 5 i.e., numbers 4, 9, 16, 25 and 36.
But if we do (36**0.5) – (4**0.5) we get 4. So to avoid this semantic error, we take n-1.
There is a little caveat. As both n and m are inclusive, if n is a perfect square, we will get an answer which is less than one the actual answer. To understand this, consider range [4, 36]. Answer is 5 i.e., numbers 4, 9, 16, 25 and 36.
But if we do (36**0.5) – (4**0.5) we get 4. So to avoid this semantic error, we take n-1.
int countOddSquares(int n, int m){ return (int)pow(m,0.5) - (int)pow(n-1,0.5);}Read full article from Number of elements with odd factors in given range - GeeksforGeeks
