# Finding intersections in a given range ?

• mohamed el teir
In summary, the conversation discusses the problem of finding the number of values in a given range that are divisible by at least one number from a given set. The solution proposed involves storing the numbers of values divisible by each number in the set and using cumulative sum to calculate the intersections. However, the issue of high time and memory complexity is raised, and it is suggested to use brute force methods or implement data structures like red black trees. Additionally, the complexity of factorization is mentioned as a potential challenge.
mohamed el teir
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.

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 ?

Well, the main I need to make sure you are aware of is the complexity of the factorization a number into its prime factors, which is so hard its used in encryption schemes. You are pretty much left with brute force methods. One thing that isn't hard to do if S is small is to produce the multiples of numbers in your set S that might fall within the range given, then you are left with a set intersection problem which has pretty fast implementations in dynamic programming and in data structures like red black trees.

Last edited:

## What is the definition of "finding intersections"?

Finding intersections refers to the process of identifying the points at which two or more lines, curves, or shapes intersect or overlap within a given range or boundary.

## Why is finding intersections important in scientific research?

Finding intersections plays a crucial role in many scientific fields, including mathematics, physics, and computer science. It allows researchers to identify relationships and patterns between different variables or phenomena, and can help validate theories and models.

## What are some common methods for finding intersections in a given range?

There are several methods for finding intersections, including graphing, algebraic manipulation, and numerical methods such as root-finding algorithms. The most appropriate method depends on the specific problem and data available.

## How do you determine the accuracy of the identified intersections?

The accuracy of the identified intersections depends on the method used and the precision of the data. In some cases, the intersections may be exact, while in others they may have a margin of error. It is important to consider the limitations and assumptions of the method used when evaluating the accuracy of the intersections.

## What are some real-world applications of finding intersections in a given range?

Finding intersections has a wide range of real-world applications, including determining the optimal route for transportation, analyzing stock market trends, and simulating the movement of celestial bodies. It is also commonly used in engineering and design to ensure the proper fit and alignment of components.

Replies
12
Views
1K
Replies
13
Views
3K
Replies
8
Views
1K
Replies
17
Views
2K
Replies
17
Views
1K
Replies
29
Views
2K
Replies
3
Views
1K
Replies
1
Views
1K
Replies
9
Views
2K
Replies
8
Views
1K