Rambo Numbers

Concepts Used

Mathematics

Difficulty Level

Hard

Problem Statement (Simplified):

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

For example, let’s assume we’re given with range([-10,30]) and r=3, there are total 14 numbers divisible by r in range. i.e [-9,-6,-3,0,3,6,9,12,15,18,21,24,27,30]

Solving Approach :

hi

1) We can find that by dividing p and q by r.
2) q/r gives total number of values divisible by r in range [1,q] ( or [ q,-1 ] if q is negative).
3) p/r gives total number of values divisible by r in range [1,p] ( or [ p,-1 ] if p is negative).
4) We can get our answer on subtracting number of values found in range [1,p] ( or [p,-1] ) from number of values found in range [1,q] ( or [q,-1] ).
5) An extra value should also be considered if following conditions are satisfied:

1) If range contains 0, we would add an additional 1, as 0 is divisible by r but is not counted by above method.
2) If p and q both values are positive and p is divisible by r.
3) If p and q both values are negative and q is divisible by r.

Example

We’ll take an example for different range cases :

Case 1: Negative to Negative

Assuming range as [-12,-2] and r=3, here p/r gives -4 and q/r gives 0, hence there are 4 numbers between range [-12,-1] i.e. [-12,-9,-6,-3]. Also there is no number in range [-2, -1], hence there are total 4 numbers which are divisible by ‘r’ in range [-12,-2].
NOTE: If range near to 0 is divisible by r, 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.

Case 2: Positive to Positive

Assuming range as [2,12] and r=3, here p/r gives 0 and q/r gives 4, hence there are 4 numbers between range [1,12] i.e. [3,6,9,12]. Also there is no number in range [1,2], hence there are total 4 numbers which are divisible by ‘r’ in range [2, 12].
NOTE: If range near to 0 is divisible by r, 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.

Case 3: Negative to Positive

Assuming range as [-12,12] and r=3, here p/r gives -4 and q/r gives 4, hence there are 4 numbers between range [-12, 1] i.e. [3,6,9,12]. Also there are 4 numbers in range [1,12]. Also, 0 is also divisible by 3, so it will be included as well as. Hence there are total 9 numbers which are divisible by ‘r’ in range [-12, 12].

Solutions

import java.util.*;
import java.io.*;

public class Main {
  
  static long count(long r, long p, long q ){
  
    if((p>0 && p%r==0)|| (p==0 || q==0) || (q<0 && p<0 && q%r==0) ||( p<0 && q>0) )
      return (q/r)-(p/r)+1;
    else
      return (q/r)-(p/r);

  }

  
  public static void main(String args[]) throws IOException {
    Scanner sc = new Scanner(System.in);
    int test = sc.nextInt();
  
    while(test--!=0){
      
      long r = sc.nextLong(), p = sc.nextLong(), q = sc.nextLong();
      
      System.out.println(count(r,p,q));
    }  
    
  }
}
Previous post Top 50 C Programming Interview Questions and Answers
Next post Sliding Window

Leave a Reply

Your email address will not be published. Required fields are marked *