# Smart phone problem! Basic DSA Learning series

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.

3 Likes
``````/* 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.

@suman_18733097

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.

1 Like

Thank you so much!