{"id":789,"date":"2020-06-11T10:14:21","date_gmt":"2020-06-11T10:14:21","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=789"},"modified":"2022-06-17T09:20:44","modified_gmt":"2022-06-17T09:20:44","slug":"total-numbers-divisible-by-a-number-in-a-given-range","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/total-numbers-divisible-by-a-number-in-a-given-range\/","title":{"rendered":"Total numbers divisible by a number in a given range"},"content":{"rendered":"

<\/p>\n

Concepts Used:<\/h3>\n
\n

Mathematics<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

Problem Statement (Simplified):<\/h3>\n
\n

For given three numbers r<\/code>,p<\/code>,q<\/code>. We have to find the total number of values divisible by r<\/code> in a range [p<\/code>,q<\/code>]. (Both Inclusive). <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Test Case:<\/h4>\n
Input:\n1\n3 -10 30\n\nOutput:\n14\n\nExplaination:\nThere are total 14<\/code> numbers divisible by 3<\/code> in range [-10,30], that are [-9,-6,-3,0,3,6,9,12,15,18,21,24,27,30]<\/code><\/code><\/pre>\n
Solving Approach :<\/h3>\n
Bruteforce Approach:<\/strong><\/p>\n
\n
1) We can start a loop from p<\/code> to q<\/code>, and then check if the current value is divisible by r<\/code> or not, if yes, we increase the counter by 1.
\n2) After all numbers in a given range are iterated, we print the count.
\n3) This approach takes O(q-p)<\/code> time complexity for a given range. But this approach is inefficient for larger ranges and a larger number of queries. So we move to a more efficient approach.<\/p>\n<\/blockquote>\n
Efficient Approach:<\/strong><\/p>\n
    \n
  1. We can find that by dividing p<\/code> and q<\/code> by r<\/code>.<\/li>\n
  2. q\/r<\/code> gives total number of values divisible by r<\/code> in range [1,q<\/code>] ( or [ q,-1<\/code> ] if q<\/code> is negative).<\/li>\n
  3. p\/r<\/code> gives total number of values divisible by r<\/code> in range [1,p<\/code>] ( or [ p,-1<\/code> ] if p<\/code> is negative).<\/li>\n
  4. We can get our answer on subtracting number of values found in range [1,p<\/code>] ( or [p,-1<\/code>] ) from number of values found in range [1,q<\/code>] ( or [q,-1<\/code>] ).<\/li>\n
  5. An extra value should also be considered if following conditions are satisfied:
    \na. If range contains 0<\/code>, we would add an additional 1, as 0<\/code> is divisible by r<\/code> but is not counted by above method.
    \nb.If p<\/code> and q<\/code> both values are positive and p<\/code> is divisible by r<\/code>.
    \nc. If p<\/code> and q<\/code> both values are negative and q<\/code> is divisible by r<\/code>.<\/li>\n<\/ol>\n
    Example:<\/h4>\n
    \n
    We’ll take an example for different range cases :<\/p>\n
    Case 1: Negative to Negative<\/em><\/strong>  <\/p>\n
    Assuming range as [-12,-2] and r=3<\/code>, here   gives -4<\/code> and  gives 0<\/code>, hence there are 4<\/code> numbers between range [-12,-1]<\/code> i.e. [-12,-9,-6,-3]<\/code>. Also there is no number in range [-2, -1]<\/code>, hence there are total 4<\/code> numbers which are divisible by ‘r’ in range [-12,-2]<\/code>.
    \nNOTE:<\/em><\/strong> If range near to 0 is divisible by r<\/code>, we add additional 1 to answer, that it is counted in both ranges i.e. [p,-1] and [q,-1] and on substraction, it is discarded, so we add an extra 1 in answer for it.<\/p>\n
    Case 2: Positive to Positive<\/em><\/strong>  <\/p>\n
    Assuming range as [2,12] and r=3<\/code>, here   gives 0<\/code> and  gives 4<\/code>, hence there are 4<\/code> numbers between range [1,12]<\/code> i.e. [3,6,9,12]<\/code>. Also there is no number in range [1,2]<\/code>, hence there are total 4<\/code> numbers which are divisible by ‘r’ in range [2, 12]<\/code>.
    \nNOTE:<\/em><\/strong> If range near to 0 is divisible by r<\/code>, we add additional 1 to answer, that it is counted in both ranges i.e. [1,p] and [1,q] and on substraction, it is discarded, so we add an extra 1 in answer for it.<\/p>\n
    Case 3: Negative to Positive<\/em><\/strong><\/p>\n
    Assuming range as [-12,12] and r=3<\/code>, here   gives -4<\/code> and  gives 4<\/code>, hence there are 4<\/code> numbers between range [-12, 1]<\/code> i.e. [3,6,9,12]<\/code>. Also there are 4<\/code> numbers in range [1,12]<\/code>. Also, 0<\/code> is also divisible by 3<\/code>, so it will be included as well as. Hence there are total 9<\/code> numbers which are divisible by ‘r’ in range [-12, 12]<\/code>.  <\/p>\n<\/blockquote>\n
    Solutions:<\/h3>\n\t\t\t\t\t\t