-3

I was asked this question in an interview.Asked me to sum an Integer Array like Fibonacci series type.

Like if we add array[]={2,6,3,1} output should be 31.

2+6=8, 8+3=11, 11+1=12, now add 8+11+12 = 31?

How can I do this in Java?

Wai Ha Lee
  • 8,598
  • 83
  • 57
  • 92
PritamGhosh
  • 1
  • 1
  • LoL! Show your attempt(pseudo-code). – Forkmohit Dec 05 '15 at 16:25
  • help will always be given at hogwarts...It is just not the proper way to ask question...Provide the code snippet that you got... – Naruto Dec 05 '15 at 16:28
  • 1
    It should take an array of size one less than original...keep on storing sum everytime into it...Then sum all elements using int sum = Arrays.stream(myIntArray) .sum(); – Naruto Dec 05 '15 at 16:33
  • 1
    @Naruto, that is memory inefficient though. It can be done in `O(1)` memory. – Emz Dec 05 '15 at 16:59
  • Scala solution: `Seq(2,6,3,1).scanLeft(0)(_+_).drop(2).sum`. Converting to Java: exercise for the reader. – Chris Martin Dec 05 '15 at 22:21

1 Answers1

1

This was fun! The easiest solution to come up with is to use nested fors and iterate over adding only if the previous value.

However, if we think about it, your example is linear, couldn't it be done in linear? Yes it could. So we now know we have to use only one (nested) for. We have to keep track of the values that we've added together, in your example {2,6}, {2,6,3} and {2,6,3,1}, so we can use a another Array for that with a size one less than the input Array.

However, can't we add them directly? Instead of storing every value we calculate we just store the previous one and the sum so far, the result:

public static int arrFibSum (int arr[]) {
    int sum = 0;

    for (int i = 0; i < arr.length-1; i++) {
        sum += sum + arr[i+1];
    }

    return sum;
}

It takes an Array, like yours {2,6,3,1}

  1. Sets the previous value, to the last calculated value.

  2. Calculate the next value based on the previous and the next.

In this example it prints out: 31.

For the future: Try to write some psuedo-code. You wrote down one example try to write it generic and finally you are ready to start to implement it.

There is a reason why I tried to write the process step by step above.

Updated from Erik's comment.

Emz
  • 1,280
  • 1
  • 14
  • 29
  • You are welcome. Now do me two favors (in order of importance): Reflect on your question and the problem. Then accept (if and only if it fully answered your question) and/or upvote (if it helped you to get an answer or was generally useful to you). – Emz Dec 05 '15 at 16:58
  • @Droidman, at least you made me smile! :) -- Think I am going to steal that image from now on! -- 34M points? Jon Skeet has been slacking. – Emz Dec 05 '15 at 17:18
  • 1
    The value given `prev` in `prev += arr[i];` is never used. That line can be deleted without consequence. – Erick G. Hagstrom Dec 05 '15 at 20:05
  • @ErickG.Hagstrom you are very much correct. Updated to reflect that. – Emz Dec 05 '15 at 21:38
  • I like it. Very clean. :-) – Erick G. Hagstrom Dec 06 '15 at 19:46