EXAMPLE 1) 1 10 2 2
a,d=2 a,a+d,a+2d,a+3d,a+4d are all multiple of 2 , so basically you need to count elements which are multiple of 2 and then subtract from the 1-10 range(inclusive) number of elements multiple of of 2 = (m/2) = 10/2 = 5 range = ( m - n) + 1 = 10 number of elements not multiple of 2 = range - 5 = 10 - 5 = 5(ans) EXAMPLE 2) 20 100 3 3 a,d=3 same as above case a,a+d,a+2d,a+3d,a+4d all are multiple of 3 number of elements multiple of of 3(1..to..100) = (m/2) = 100/3 = 33 now 33 includes elements which lies b/w 1-19 , but we dont want those count so remove those count.. number of elements multiple of of 3(1..to..19) =(n-1)/2 = (19/2) = 6 desired count lies b/w range (20-100) = 33 - 6 = 27 range = ( m - n) + 1 = 81 number of elements not multiple of 3 = range - 27 = 81 - 27 = 54 (ans) so we just applying general formula :- n(A U B) =n(A) + n(B) - n(A intersection B) but in above 2 examples both a and d were same or could be multiple of each other....this is a simple scenario . EXAMPLE 3) 20 100 2 3 suppose a = 2 , d = 3 now i am considering only a and a+d ...just to give you the idea.. so we need to find elments b/w 20-100 not divisible by 2 and 5. using same method as above :- elements divisible by 2 = 41 elements divisible by 5 = 17 total elements = 41 + 17 = 58 but some number are include twice in 58 ....number which are multiple of both 2 and 5 i.e once by calculating counts for 2 and another while calculating count for 5. eg 10 = 5 x 2 , 20 = 4 x 5...etc.. so now we want to remove these double inclusion i.e calculating n(A intersecting B). which is nothing but same as counting elements divisible by ( a X a+d ) i.e 2 X 5 =10 by same method :- elements divisible by 10 = 9 correct count of elements in range (20-100) = 58 - 9 = 49 number of elements not multiple of 2 or 5 = 81 - 49 = 32 (ANS) now i hope you got the idea.... -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
