Why i have to use long in array type even it is mentioned that the array items is mentioned 1 and 10^8 inclusive?

The integer can hold 2 x 10^9 right?

While computing the answer, the trivial thing you would do is:

- Sort the Array Integers in Non-Decreasing Order
- Initialise your answer to 0
- Iterate over the array elements
- Consider the budget of i^{th} element as price, the revenue you would get is

`budget[i] * (n - i)`

. - Update the answer accordingly

Note that both `budget[i]`

and `(n - i)`

are integers. In C, CPP and Java, the result is automatically typecasted to int. This can lead to overflow if both `budget[i]`

and `(n - i)`

are high, resulting in the product exceeding the limit of int.

Of course, the statement can also be written as

`budget[i] * ((long long int)(n - i))`

, which doesnâ€™t require using an array of Long Integers.

```
/* package codechef; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static long maxRevenue(int n, int[] budgets) {
long maxRevenue = Long.MIN_VALUE;
Arrays.sort(budgets);
for(int i = 0; i < n; i++) {
long sum = budgets[i] * (n - i);
maxRevenue = Math.max(maxRevenue, sum);
}
return maxRevenue;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] budgets = new int[N];
for(int i = 0; i < N; i++) {
budgets[i] = scanner.nextInt();
}
System.out.println(maxRevenue(N, budgets));
}
}
```

This works when i convert the input array into long.

```
long[] budgets = new long[N];
```

But each customersâ€™ budget is between 1 and 108, inclusive right which is on the integer limitâ€¦

Why we have to use long to get input values?

And i also have used long datatype while multiplication?

` long sum = budgets[i] * (n - i);`

Note that the question is already answered.

Iam storing this multiplication value on long variable right??

```
long sum = (long) budgets[i] * (n - i);
```

Oh so even though i used long sum variable to store the multiplication, i have to explicitly convert the budgets[i] * (n - i) to long datatype.

I thought that using long sum will handle the integer overflow, So we have to care also the numbers that we are multiplying whether they are integer.

Yeah, see the following for better understanding.

```
int a = ((int)(1e9));
int b = ((int)(1e9));
int c = a * b; // Integer Overflow occurs here
// ***********
int a = ((int)(1e9));
int b = ((int)(1e9));
long long int c = a * b; // Integer overflow occurs here too
// ***********
int a = ((int)(1e9));
int b = ((int)(1e9));
long long int c = (long long int)(a * b); // Again Integer overflow
// ***********
int a = ((int)(1e9));
int b = ((int)(1e9));
long long int c = ((long long int)(a)) * b; // No overflow
// ***********
long long int a = ((int)(1e9));
long long int b = ((int)(1e9));
long long int c = a * b; // No overflow
```

Points to note:

The result of an arithmetic expression is automatically typecasted to the largest data type present in operands.

Example:

If a and b both are int, a \oplus b will be int.

If one of a and b is long, a \oplus b will be long

If one of a and b is float, a \oplus b will be float.

If both are long, a \oplus b will be long \dots and so on.

You might want to explore on this topic by your self to understand it more clearly. Also, a Long Integer is recommended when working on bits.

Thank you so much!