Smart phone problem! Basic DSA Learning series

1

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

2

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
3 
/* 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);
4

Note that the question is already answered.

5

Iam storing this multiplication value on long variable right??

6 
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

7

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
8

Thank you so much!