Finding sequence that maps to a given sum

  • Thread starter Thread starter hholzer
  • Start date Start date
  • Tags Tags
    Sequence Sum
AI Thread Summary
To find indices i and j in an array A such that the sum of A[i..j] equals a given number s, the discussion explores potential methods, including the use of a hashtable and aggregate arrays. While a hashtable could facilitate a linear time solution, participants note that achieving linear time complexity may not be feasible due to the need to explore multiple options. The conversation highlights the challenge of searching for the required sum while considering the monotonic nature of the series. An approach involving creating a table upfront is mentioned, though it results in a quadratic time complexity. Overall, the consensus is that while various strategies exist, a truly linear time solution remains elusive.
hholzer
Messages
36
Reaction score
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
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.
 
Thread 'Is this public key encryption?'

Thread 'Is this public key encryption?'

I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
View full post »

Thread 'Who is responsible for the software when AI takes over programming?'

I tried a web search "the loss of programming ", and found an article saying that all aspects of writing, developing, and testing software programs will one day all be handled through artificial intelligence. One must wonder then, who is responsible. WHO is responsible for any problems, bugs, deficiencies, or whatever malfunctions which the programs make their users endure? Things may work wrong however the "wrong" happens. AI needs to fix the problems for the users. Any way to...
View full post »

Similar threads

Python Simple code example of transforming matrix into upper triangular form
Replies
3
Views
1K
How to analyse a sequence of vehicle states?
Replies
7
Views
2K
Debugging a Backprop Neural Network: Issues & Solutions
Replies
3
Views
2K
Python Thermal lattice Boltzmann model ignoring source term -- python code help please
Replies
1
Views
2K
Python How can we iteratively create sublists from a list based on a sum threshold?
Replies
5
Views
1K
Java Do we have a concept(?) called 'Hashfunction' in 'Hashtable' in Java?
Replies
2
Views
2K
Where is my logic wrong in this dynamic programming problem?
Replies
2
Views
2K
Fortran Using Integer Expressions in an If Statement: Help Needed!
Replies
3
Views
2K
Python Optimizing Prime Pair Combinations for Project Euler Problem 60
2
Replies
97
Views
8K
Finding intersections in a given range ?
Replies
1
Views
933

Hot Threads

Recent Insights

Back
Top