CODEWITHSUNDEEP
javaarrayscollections
James
James

Reputation: 5

Why does this method fail?

Recently ran into this question in an interview. Given an array of integers, find the smallest integer x that can be used as a starting point so that when you add each number from the array to the running total, the running total never goes below 1. The function stub they gave me, for Java, took in a list collection and I was supposed to return a long. This solution to me seems like it has to work, but failed every test case. Why?

public static long minStart(List<Integer> arr) {
    long minStart = 0;
    long runningTotal = minStart;
    for(int i = 0; i<arr.size(); i++){
        runningTotal += arr.get(i);
        if(runningTotal<1){
            minStart++;
            i = 0;
            runningTotal = minStart;
        }
    }
    return minStart;
}

Upvotes: 0

Views: 546

Answers (2)

Bohemian
Bohemian

Reputation: 425003

Your problem here is the if block - you should not have one.

I also suspect you misunderstood the question, which I read as return 1 - the minimum of the running total.

Something like this:

public static long minStart(List<Integer> arr) {
    long total = 0; // long to avoid integer overflow
    long min = Long.MAX_VALUE;
    for (int n : arr) {
         total += n;
         min = Math.min(min, total);
    }
    return 1 - min;
}

To further reduce the amount of code, you could replace the loop with just:

for (int n : arr)
     min = Math.min(min, total += n);

This may or may not impress, depending on your audience.

Upvotes: 0

Charlie Armstrong
Charlie Armstrong

Reputation: 2342

The issue here is that in your for loop, you use i = 0; to reset, but then on the very next iteration, the for loop is going to increment i to equal 1, which means you skipped over the first number in the list. I would just try simply changing that line to be i = -1;.

Upvotes: 1

Related Questions