phantomlord
BAN USER@ninhnnsoc, here you go :-) Test cases included. Don't get me wrong, your solution is very neat, does the job in one loop. Hence a lot of scrutiny.
public class ContinuousSequenceSum {
public static boolean sumsTo(int[] a, int T) {
int wL = 0, wR = 0, sum = a[0];
while (wR < a.length) {
if (sum < T) {
if (wR < a.length-1) ++wR;
else return false;
sum += a[wR];
}
if (sum==T) return true;
if (sum > T) {
sum -= a[wL];
++wL;
}
}
return false;
}
public static void main(String[] args) {
int[] a1 = {23, 5, 4, 7, 2, 11};
int t1 = 20;
System.out.println(sumsTo(a1, t1)); // true
int[] a2 = {1, 3, 5, 23, 2};
int t2 = 8;
System.out.println(sumsTo(a2, t2)); // true
int[] a3 = {1, 3, 5, 23, 2};
int t3 = 7;
System.out.println(sumsTo(a3, t3)); // false
int[] b1 = {23, 5, 12, 4, 7, 9};
int u1 = 20;
System.out.println(sumsTo(b1, u1)); // true
int[] b2 = {1, 2, 23, 24, 20, 4, 7, 9};
int u2 = 20;
System.out.println(sumsTo(b2, u2)); // true
int[] b3 = {25, 23, 24, 20, 4, 7, 9};
int u3 = 20;
System.out.println(sumsTo(b3, u3)); // true
int[] b4 = {1, 2, 3, 4, 20, 21, 5, 9, 6};
int u4 = 20;
System.out.println(sumsTo(b4, u4)); // true
}
}
@ninhnnsoc, OK, I realised the second comment was invalid after writing and deleted it.
There is one more bug. Feed the input [1, 3, 5, 23, 2], 7.
The sum is 2 at the last index because everything up to that point does not add up to 7. Because the sum is 2, it increments wR which goes over the bounds of the array and when accessing it to accumulate the next sum, the position is N, hence invalid. You'll probably need to return false if wR is == N after incrementing to prevent that.
Do rand(5) up to 7 times.
1. rand(5) -> if it is 1, return 1.
2. rand(5) -> if it is 1, return 2.
3. rand(5) -> if it is 1, return 3.
4. rand(5) -> if it is 1, return 4.
5. rand(5) -> if it is 1, return 5.
6. rand(5) -> if it is 1, return 6.
7. rand(5) -> if it is 1, return 7.
Uses recursion and iterators, hence avoids calling get(int index) method which is inefficient.
public static List<Integer> merge(List<Integer> listA, List<Integer> listB)
{
if (listA == null) return listB;
if (listB == null) return listA;
final ListIterator<Integer> iterA = listA.listIterator(0);
final ListIterator<Integer> iterB = listB.listIterator(0);
final List<Integer> result = new LinkedList<Integer>();
merge(iterA, iterB, result);
return result;
}
private static void merge(ListIterator<Integer> iterA,
ListIterator<Integer> iterB,
List<Integer> result)
{
if (!iterA.hasNext())
{
while (iterB.hasNext()) { result.add(iterB.next()); }
return;
}
if (!iterB.hasNext())
{
while (iterA.hasNext()) {result.add(iterA.next()); }
return;
}
Integer a = iterA.next();
Integer b = iterB.next();
if (a < b)
{
result.add(a);
b = iterB.previous(); // rewind
}
else if (b < a)
{
result.add(b);
a = iterA.previous(); // rewind
}
else
{
result.add(a);
result.add(b);
}
merge(iterA, iterB, result);
}
The get(int index) method of List is not efficient. It starts from the head or the tail to get the next element every time it is called, making it O(N^2). It is better to use an iterator.
- phantomlord December 01, 2014How do you merge-sort a linked list?
- phantomlord December 01, 2014How does the MinHeap solution work in O(N) time?
- Building the heap, i.e., inserting and deleting takes O(log N) time.
- When you are done building the heap which now maintains the largest 1000 elements, you need to extract these elements from the heap. To extract them, you need to call 'delete' 1000 times. That makes the complexity O(1000 log N) which is linearithmic.
This solution works.
It uses Binary Search and checks if A[mid] and A[mid+1] are in order. Based on that, it decides which half of the array it should continue to search – if they are in order, the max must be on the right. If they are not in order, then the max must be on the left.
Stack uses an extra memory that is proportional to the number of words in the given string, hence it uses O(N).
- phantomlord March 06, 2015