Finding sequence that maps to a given sum

In summary, to find i,j in array A that have a sum of s, the conversation suggests using a hashtable or creating an aggregate array (n time). However, it is not possible to achieve linear time. Another option is to make a table at the beginning and eat n^2.
  • #1
hholzer
37
0
given array A and number s, find i,j so sum of A[i..j] = s

Can this be done in linear time? I've thought of using a hashtable
but I would be interested in other methods.
 
Technology news on Phys.org
  • #2
Hmm -- you could create an aggregate array to start (n time). But I don't think you can get away from trying all of the options, sumsInArray>s, and doing a search for the difference you want (the series you are searching is monotonic so that should help). That doesn't get you to linear yet though. n + n(s>S)*log(n(s<S))

If you don't mind making a table at the get go and eating n^2, then that would work.
 

Related to Finding sequence that maps to a given sum

What is the purpose of finding a sequence that maps to a given sum?

The purpose of finding a sequence that maps to a given sum is to solve mathematical problems and puzzles, as well as to analyze and understand patterns and relationships between numbers. It is also useful in various fields such as computer science, cryptography, and genetics.

What is the process of finding a sequence that maps to a given sum?

The process of finding a sequence that maps to a given sum involves identifying the sum that needs to be achieved, determining the range of numbers to be used, and then finding a combination of numbers that add up to the given sum. This can be done through manual calculation or by using algorithms and programming techniques.

What are some common techniques used to find a sequence that maps to a given sum?

Some common techniques used to find a sequence that maps to a given sum include brute force method, dynamic programming, backtracking, and divide and conquer. These techniques can be used alone or in combination depending on the specific problem at hand.

What are the challenges of finding a sequence that maps to a given sum?

One of the main challenges of finding a sequence that maps to a given sum is that there may be multiple solutions or no solution at all. This can make the problem more complex and require more advanced techniques to find the desired sequence. Additionally, the size of the given sum and the range of numbers can also affect the difficulty of the problem.

How is the concept of finding a sequence that maps to a given sum applied in real-world scenarios?

The concept of finding a sequence that maps to a given sum is applied in various real-world scenarios such as in financial transactions, data encryption, and DNA sequencing. It is also used in algorithms for optimizing resource allocation, scheduling tasks, and solving optimization problems in engineering and computer science.

Similar threads

  • Programming and Computer Science
Replies
7
Views
702
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
5
Views
959
  • Programming and Computer Science
Replies
1
Views
807
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
17
Views
1K
  • Programming and Computer Science
3
Replies
97
Views
7K
  • Programming and Computer Science
Replies
12
Views
3K
  • Programming and Computer Science
Replies
1
Views
1K
Back
Top