find the sum of all the numbers in the Fibonacci series that are smaller or equal to that number

Question

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 . . .

Given a specific number in this series Fn, your program needs to find the sum of all the numbers in the Fibonacci series that are smaller or equal to that number.

Input Format Your program will be provided a number in the Fibonacci series on STDIN.

Constraints

0<<Fn<100000

Sample Input

Sample Output

The output for above input (8) should be 0 + 1 + 1 + 2 + 3 + 5 + 8
20

To solve above problem I write a code like

import java.util.*;
import java.lang.*;
import java.io.*;

class MyTest{
    public static Integer solveProblem(int n) {
        if (n>=0 || n<100000) {
        int fibo[] = new int[n+1];
        fibo[0] = 0; fibo[1] = 1;
        int sum = fibo[0] + fibo[1];
        for (int i=2; i<=n; i++) {
            fibo[i] = fibo[i-1]+fibo[i-2];
            if(n >= fibo[i]) {
                sum += fibo[i];
            } else {
                break;
            }
        }
        return sum;
        } else {
            return 0;    
        }
    }

    public static void main (String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        int sum = MyTest.solveProblem(in.nextInt());
        System.out.println("This is the output:"+sum);
    }
}

I run the program it works fine with the sample test case as mentioned but when I submit this program on online test quiz then it run with their test case and it will fail.

Is something wrong in my program or I didn't understand the question properly. Please help me to find out exact answer of this problem.

Well, you don't use the scanner to get the value, you set "8" in parameter. — AxelH, Jun 08 '17 at 06:11
I changed and read input from scanner but still not accpeting — Kushal Jain, Jun 08 '17 at 06:13
It's hard to tell since you are not providing an example test case that fails. — 1615903, Jun 08 '17 at 06:13
I dont know those test cases, they run their test cases but not showing to me what input they are tested — Kushal Jain, Jun 08 '17 at 06:15
Well, you could try to fix the constraint that I pointed out and try again. — 1615903, Jun 08 '17 at 06:17
see https://stackoverflow.com/questions/8965006/java-recursive-fibonacci-sequence - usually solved through recursion — Scary Wombat, Jun 08 '17 at 06:17
If you try with `n=0`, you get an array of `int[1]` then try to access `array[1]` -> exception — AxelH, Jun 08 '17 at 06:18
see https://en.wikipedia.org/wiki/Fibonacci_number the eight element is `21` `20` does not appear — Scary Wombat, Jun 08 '17 at 06:23
@ScaryWombat, read again, it is doing the sum of every fibonnaci numbers smaller or equals to the input, not getting that specific value ;-) so `1+1+2+3+5+8 = 20` — AxelH, Jun 08 '17 at 06:25

score 3 · Accepted Answer · answered Jun 08 '17 at 06:23

Your code seems to fail for n=0 and n=1.

For n=1 you return 1 but should return 2 (since there are two elements whose value is 1, and you should be adding both of them to the sum).
For n=0 you are throwing an exception.

You could fix this by adding a special check for these cases:

public static Integer solveProblem(int n) {
    if (n==0) 
        return 0;
    else if (n==1) 
        return 2;
    else if (n>=0 || n<100000) {
        int fibo[] = new int[n+1];
        fibo[0] = 0; fibo[1] = 1;
        int sum = fibo[0] + fibo[1];
        for (int i=2; i<=n; i++) {
            fibo[i] = fibo[i-1]+fibo[i-2];
            if(n >= fibo[i]) {
                sum += fibo[i];
            } else {
                break;
            }
        }
        return sum;
    } else {
        return 0;    
    }
}

How yeah, didn't notice the problem with `n = 1` ! Nice catch. — AxelH, Jun 08 '17 at 06:27

AxelH · Answer 2 · 2017-06-08T06:28:48.630

1

You should get the value from the Scanner

Scanner in = new Scanner(System.in);
int sum = MyTest.solveProblem(8);

by using Scanner.nextInt()

Scanner in = new Scanner(System.in);
int sum = MyTest.solveProblem(in.nextInt());

If you input a value of 0, it is accepted by your condition but you create an array of size 1, then try to access the second value -> ArrayIndexOutOfBoundsException

int fibo[] = new int[n+1];
fibo[0] = 0; 
fibo[1] = 1; //HERE, exception as there is not `fibo[1]`

Update the condition to

if ( n > 0 && n < 100000) //note the && to correct your logic error too

NOTE : I don't think this is a good idea to use an array here since you are using a big array that is not necessary (not fully used), using two variables (last, current) would be simpler.

edited Jun 08 '17 at 06:28

answered Jun 08 '17 at 06:12

AxelH

14,325
2
25
55

Hey, I changed and read the input using scanner but still not accpeting – Kushal Jain Jun 08 '17 at 06:14
1

To the downvoters, please note that OP have edited his question as this was a first problem ... I will add the rest of the solution once we have it! – AxelH Jun 08 '17 at 06:17

score 0 · Answer 3 · answered Oct 03 '17 at 18:46

import java.util.*;
import java.lang.*;
import java.io.*;

class CutShort
{
    public static long solveProblem(int input) {        

        long sum = 0;        

        long finalstate = 1;
        long currentstate = 0;

        while(finalstate<=input) {

            sum = sum+finalstate;

            long add = currentstate + finalstate;

            currentstate = finalstate;

            finalstate = add;
        }
        return sum;

    }


public static void main (String[] args) throws java.lang.Exception

    {

        Scanner in = new Scanner(System.in);

        /*Parse input here*/

        System.out.println("Enter you Input");

        int input = in.nextInt();

        long output = 0;

        if(input>0 && input<100000)

        output = solveProblem(input);

        System.out.println("This is the output" + output);

    }

}

find the sum of all the numbers in the Fibonacci series that are smaller or equal to that number

3 Answers3