Time to solve: 48 hours.
When you went undercover in Commander Lambda's organization, you set up a coded messaging system with Bunny Headquarters to allow them to send you important mission updates. Now that you're here and promoted to Henchman, you need to make sure you can receive those messages - but since you need to sneak them past Commander Lambda's spies, it won't be easy!
Bunny HQ has secretly taken control of two of the galaxy's more obscure numbers stations, and will use them to broadcast lists of numbers. They've given you a numerical key, and their messages will be encrypted within the first sequence of numbers that adds up to that key within any given list of numbers.
Given a non-empty list of positive integers l and a target positive integer t, write a function answer(l, t) which verifies if there is at least one consecutive sequence of positive integers within the list l (i.e. a contiguous sub-list) that can be summed up to the given target positive integer t (the key) and returns the lexicographically smallest list containing the smallest start and end indexes where this sequence can be found, or returns the array [-1, -1] in the case that there is no such sequence (to throw off Lambda's spies, not all number broadcasts will contain a coded message).
For example, given the broadcast list l as [4, 3, 5, 7, 8] and the key t as 12, the function answer(l, t) would return the list [0, 2] because the list l contains the sub-list [4, 3, 5] starting at index 0 and ending at index 2, for which 4 + 3 + 5 = 12, even though there is a shorter sequence that happens later in the list (5 + 7). On the other hand, given the list l as [1, 2, 3, 4] and the key t as 15, the function answer(l, t) would return [-1, -1] because there is no sub-list of list l that can be summed up to the given target value t = 15.
To help you identify the coded broadcasts, Bunny HQ has agreed to the following standards:
- Each list l will contain at least 1 element but never more than 100.
- Each element of l will be between 1 and 100.
- It will be a positive integer, not exceeding 250.
- The first element of the list l has index 0.
- For the list returned by answer(l, t), the start index must be equal or smaller than the end index.
Remember, to throw off Lambda's spies, Bunny HQ might include more than one contiguous sublist of a number broadcast that can be summed up to the key. You know that the message will always be hidden in the first sublist that sums up to the key, so answer(l, t) should only return that sublist.
To provide a Python solution, edit solution.py
To provide a Java solution, edit solution.java
Inputs:
(int list) l = [4, 3, 10, 2, 8]
(int) t = 12
Output:
(int list) [2, 3]
Inputs:
(int list) l = [1, 2, 3, 4]
(int) t = 15
Output:
(int list) [-1, -1]
Your code will be compiled using standard Java 7. It must implement the answer() method in the solution stub.
Execution time is limited. Some classes are restricted (e.g. java.lang.ClassLoader). You will see a notice if you use a restricted class when you verify your solution.
Third-party libraries, input/output operations, spawning threads or processes and changes to the execution environment are not allowed.
Your code will run inside a Python 2.7.6 sandbox.
Standard libraries are supported except for bz2, crypt, fcntl, mmap, pwd, pyexpat, select, signal, termios, thread, time, unicodedata, zipimport, zlib.