# Smart phone problem! Basic DSA Learning series

**URL:** <https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014>\
**Category:** Uncategorized\
**Created:** [April 14, 2021, 10:15am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014 "2021-04-14T10:15:07Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![devbikash07](https://discuss.codechef.com/user_avatar/discuss.codechef.com/devbikash07/32/30029_2.png) [@devbikash07](https://discuss.codechef.com/u/devbikash07)\
**Post date:** [April 14, 2021, 10:15am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/1 "2021-04-14T10:15:07Z")

</div>

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](https://www.codechef.com/LRNDSA01/problems/ZCO14003)

---

<div class="post-metadata">

**Author:** ![suman\_18733097](https://discuss.codechef.com/user_avatar/discuss.codechef.com/suman_18733097/32/218666_2.png) [@suman\_18733097](https://discuss.codechef.com/u/suman_18733097)\
**Post date:** [April 14, 2021, 10:31am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/2 "2021-04-14T10:31:15Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![devbikash07](https://discuss.codechef.com/user_avatar/discuss.codechef.com/devbikash07/32/30029_2.png) [@devbikash07](https://discuss.codechef.com/u/devbikash07)\
**Post date:** [April 14, 2021, 10:43am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/3 "2021-04-14T10:43:50Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![suman\_18733097](https://discuss.codechef.com/user_avatar/discuss.codechef.com/suman_18733097/32/218666_2.png) [@suman\_18733097](https://discuss.codechef.com/u/suman_18733097)\
**Post date:** [April 14, 2021, 10:45am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/4 "2021-04-14T10:45:05Z")

</div>

> [@devbikash07](#):
>
> Why we have to use long to get input values?

Note that the question is already answered.

---

<div class="post-metadata">

**Author:** ![devbikash07](https://discuss.codechef.com/user_avatar/discuss.codechef.com/devbikash07/32/30029_2.png) [@devbikash07](https://discuss.codechef.com/u/devbikash07)\
**Post date:** [April 14, 2021, 10:46am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/5 "2021-04-14T10:46:28Z")

</div>

> [@suman\_18733097](#):
>
> 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.

Iam storing this multiplication value on long variable right??

---

<div class="post-metadata">

**Author:** ![devbikash07](https://discuss.codechef.com/user_avatar/discuss.codechef.com/devbikash07/32/30029_2.png) [@devbikash07](https://discuss.codechef.com/u/devbikash07)\
**Post date:** [April 14, 2021, 10:51am UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/6 "2021-04-14T10:51:46Z")

</div>

```
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

---

<div class="post-metadata">

**Author:** ![suman\_18733097](https://discuss.codechef.com/user_avatar/discuss.codechef.com/suman_18733097/32/218666_2.png) [@suman\_18733097](https://discuss.codechef.com/u/suman_18733097)\
**Post date:** [April 14, 2021, 12:17pm UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/7 "2021-04-14T12:17:59Z")

</div>

> [@devbikash07](#):
>
> So we have to care also the numbers that we are multiplying whether they are integer.

Yeah, see the following for better understanding.

```auto
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.

---

<div class="post-metadata">

**Author:** ![devbikash07](https://discuss.codechef.com/user_avatar/discuss.codechef.com/devbikash07/32/30029_2.png) [@devbikash07](https://discuss.codechef.com/u/devbikash07)\
**Post date:** [April 14, 2021, 2:23pm UTC](https://discuss.codechef.com/t/smart-phone-problem-basic-dsa-learning-series/88014/8 "2021-04-14T14:23:31Z")

</div>

Thank you so much!
