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?

Problem: CodeChef: Practical coding for everyone

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.*;

/* 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;


    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(;

    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.

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!