-2

constraint-in java, should use array, sum should be calculated when position is even and a[i] 


import java.util.*;
class abc
{
  public static void main(String[] args)
 {
    Scanner sc=new Scanner(System.in);
    int sum=0;
      int n=sc.nextInt();
      int a[]=new int[n];
      a[0]=1;
      a[1]=2;
      for(int i=2;i<n;i++)
      {
        a[i]=a[i-1]+a[i-2];
        if(a[i]<n && i%2==0)
        sum=sum+a[i];
      }
      System.out.println(sum);
  }
}

input- 50 output- -298632831

Sanyam Srivastava
  • 1
  • 2

2 Answers2

1

In java int is 4 bytes long which has range of -2,147,483,648 to 2,147,483, 647. So in your case int sum is overflowing. Because when n = 50 febonacci series gives result as 12586269025. Which is beyond the limit of int.

So you should rather use a long to hold the sum. Which is 8 bytes with limit of -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.

Even you need to use long array, because you are performing operations after assigning values to array elements. So updated code should be:

long sum = 0;
    final long a[] = new long[50];
    a[0] = 1L;
    a[1] = 2L;
    final int n = 50;
    for (int i = 2; i < n; i++) {
      a[i] = a[i - 1] + a[i - 2];
      if (a[i] < n && i % 2 == 0) {
        sum = sum + a[i];
      }
    }
    System.out.println(sum);

Note (as suggested by Mihir): long is also having limitations, so till n = 92, it will work fine. If you can have n > 92 you need to use BigInteger. Which is also having further limits. So consider these limitations in your code.

BigInteger must support values in the range -2Integer.MAX_VALUE (exclusive) to +2Integer.MAX_VALUE (exclusive) and may support values outside of that range.

Implementation note: BigInteger constructors and operations throw ArithmeticException when the result is out of the supported range of -2Integer.MAX_VALUE (exclusive) to +2Integer.MAX_VALUE (exclusive).

Gaurav Jeswani
  • 4,410
  • 6
  • 26
  • 47
  • I'd suggest recommending something like `BigInteger` over `long` because `long` will also overflow at around the 92nd fibonacci number. – Mihir Kekkar Sep 13 '19 at 19:00
  • I've used an if condition in which I will calculate sum only if a[i] is even and it's less than n. if I enter 50, it should only sum 2 8 34 right ? why does my if condition not seem to work, it would really be helpful if you explain this bit. – Sanyam Srivastava Sep 19 '19 at 16:59
  • It is sum of 3, 8, 21 corresponding to position 2, 4 and 6. – Gaurav Jeswani Sep 19 '19 at 17:09
1

Fib(50) = 12_586_269_025 (see here for example)

Java, max int: 2_147_483_647 (go there)

Short story short: use the long type, and of course:

  • learn to make a good guess about the "size" of your results
  • then learn about the constraints that types have, like their max value

In other words, the real answer is: there are limits to everything in computing. It is really crucial to understand them.

GhostCat
  • 137,827
  • 25
  • 176
  • 248
  • I've used an if condition in which I will calculate sum only if a[i] is even and it's less than n. if I enter 50, it should only sum 2 8 34 right ? – Sanyam Srivastava Sep 19 '19 at 16:59
  • My question was not just fibonacci, it was sum of even position of fibonacci series, it was a question given to me with the constraints I had mentioned. I was told to use array. I'm still unable to understand the reason behind why the if condition seems to be 'not working'. Thanks for the help though. Also @GhostCat , I didn't respond in the initial days of asking question because someone in my family passed away and I wasn't using internet then. Thought you were being rude, but then I read your bio so it's fine. – Sanyam Srivastava Sep 21 '19 at 16:13
  • I am sorry I hear that. I did not mean to be rude. It is just a too common pattern: people leave dubious content, and then walk away. When that happened to you 10, 20, 50 times you probably sometimes lose your temper. Sorry for that, and all the best wishes. – GhostCat Sep 21 '19 at 16:21