CodeForces 1101A - Solution and Explanation

You can find problem statement here : CodeForces 1101A

Problem statement explanation :

• There are q queries
• Every query has three input l,r and d.
• You have to find a positive number 'x' such that : 

            1) it is divisible by d.
            2) it is less than 'l' or greater than 'r'.
            3) it must be minimum possible number.

Example 1 :  l=9 , r=11 , d=4 .The answer is '4'.
first find some number divisible by 4.They are "4,8,12,16". Among them '4'satisfies all condition. 

1) 4 is divisible by 4
2) 4 is less than 9
3) 4 is the minimum number that satisfies previous 2 condition

Example 2 : l=7 , r=14 , d=7 .The answer is '21'.
first find some number divisible by 7.They are "7,14,21,18". Among them '7' satisfies all the condition.

1) 21 is divisible by 7 

2) 21 is greater than 14

3) 21 is the minimum number that satisfies previous 2 condition ( we can not take '7' because it is not less  than 'l=7' && not greater than 'r=14' , '14' is not also possible answer) we take '21' as answer cause it is our next minimum number.

Solution :

Naive Approach : you can run a loop to find the number that is divisible by 'd' but you will get TLE for this. because we have at max 500 queries.


Correct Approach : It is possible to find 'x' in O(1).

if you divide a number(N) by another number(M) , you will get how many number is divisible by 'M' from 1 to 'N'. for example 10 / 2 = 5 , that means from 1 to 10 there are 5 numbers(2,4,6,8,10) that are divisible by 2.

first divide l/d (for example 1) 9/4 = 2.25, it means there are 2 number (4 & 8) from 1 to 9 that are divisible by 4 , but we need the first number cause it is the minimum number which is divisible by 4. So in this case the minimum number will always be 'd'.

 if( l / d >= 1 )  
  x = d;  

what if l == d like in the example 2 , 7/7 = 1. but we can not take 7 as answer cause 7 is not less than 'l=7'. So we have to modify our previous condition, which will be :

 if( l != d && l / d >= 1)   
   x = d;  

What if l/d = 0 , that means 'x' is greater than 'r'. (for example 10 /2  = 5 , now if we want to find the next number after 10 that is divisible by 2. we have to increment 5 then multiply it with 2 , which is 6 * 2 = 12.) So in this case we first find (r / d) and increments the result then multiply it with d.

 if( l / d == 0 ) {  
   x = ( ( r / d ) + 1 ) * d;  
 }  

Complete Solution :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

int main(){ int n; cin >>n; while(n--) { int a , b , d; cin >> a >> b >> d; if(a != d && a/d >=1) { cout << d <<endl; } else { int k = b/d; cout << (k+1)*d <<endl; } } return 0; }