assume array of N (N<=100000) elements a1, a2, .... ,an, and you are given range in it L, R where 1<=L<=R<=N, you are required to get number of values in the given range which are divisible by at least one number from a set S which is given also, this set can be any subset of {1,2,....,10}. a fast way must be used because it may ask you for more than one range and more than one S (many queries Q, Q<=100000), so looping on the values each time will be very slow.(adsbygoogle = window.adsbygoogle || []).push({});

i thought of storing numbers of values divisible by each number in the big set {1,2,....,10} in 10 arrays of N elements each, and do cumulative sum to get the number of values divisible by any specific number in any range in O(1) time, for example if it requires to get number of values divisible by at least one of the following: 2,3,5, then i add the numbers of values divisible by each of them and then remove the intersections, but i didn't properly figure out how to calculate the intersections without 2^10 or 2^9 calculations each time which will be also very slow (and possibly hugely memory consuming) because it may be done 100000 times, any ideas ?

**Physics Forums - The Fusion of Science and Community**

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# C/++/# Finding intersections in a given range ?

Have something to add?

Draft saved
Draft deleted

Loading...

Similar Threads - Finding intersections given | Date |
---|---|

Can't find my Localhost Database Engine for SQL Server | Feb 16, 2018 |

C/++/# Finding duplicates algorithm | Jan 20, 2018 |

C/++/# Is there an easy way to find ints i,j,k satisfying i*j=k^2? | May 19, 2017 |

C/++/# Program to find combination of letters associated with phone | Mar 1, 2017 |

Intersection-find Data Structure | Aug 23, 2009 |

**Physics Forums - The Fusion of Science and Community**