Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Maximum Value of F(x) - VI

Easy

0/40

Average time to solve is 10m

Contributed by

2 upvotes

Problem statement

You are provided with a sorted array of integers ‘ARR’ having length ‘N’ and a function ‘F(X)’, such that:

F(X) = S + G

Where:

‘X’ = Any integer that belongs to array ‘ARR’. 
‘S’ = Number of integers in ‘ARR’ that are strictly smaller than ‘X’.
‘G’ = Number of integers in ‘ARR’ that are strictly greater than ‘X’.

For Example:

‘ARR’ = {1, 1, 1,  2, 2, 3, 4}
Let, ‘X’ = 1
     F(X) = 0 + 4 = 4 (as ‘0’ numbers of elements are smaller than ‘1’ and ‘4’ elements that are ‘2’, ‘2’, ‘3’, and ‘4’ are greater than ‘1’.
Let ‘X’ = 2
     F(X) = 3 + 2 = 5 (as ‘3’ numbers (‘1’, ‘1’, and ‘1’) are smaller than ‘2’ and ‘2’ numbers that are ‘3’, and ‘4’ are greater than ‘2’.
Let ‘X’ = 3
     F(X) = 5 + 1 = 6 (as ‘5’ numbers (three times ‘1’ and  two times ‘2’) are smaller than ‘3’ and ‘1’ number that is ‘4’ is greater than ‘3’.
Let ‘X’ = 4
    F(X) = 6 + 0 = 6 (as ‘6’ numbers (three times ‘1’, two times ‘2’, and one time ‘3’) are smaller than ‘4’ and ‘0’ numbers are greater than ‘3’.

All you have to do is to find the maximum value of ‘F(X)’.

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer ‘T’ representing the number of test cases. Then each test case follows.

The first line of each test case will contain a single integer ‘N’ that denotes the length of the array ‘ARR’.

The second line of each test case will contain ‘N’ integers representing the elements of the array ‘ARR’.

Output Format :

For each test case, print a single integer representing the maximum value of F(X).

Note:

You don't need to print the output, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
0 <= ARR[ i ] <= 10^5

Time Limit: 1 sec

Sample Input 1 :

1
7
1 1 1 2 2 3 4

Sample Output 1 :

Explanation For Sample Input 1 :

For the first test case, an explanation is given in the description.

Sample Input 2 :

2
5
10 20 30 40 40
2
3 4

Sample Output 2 :

4
1

Hint 1

Hint 2

Hint 3

Consider each element as the value of ‘X’ and calculate the value of F(X) for every case.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force

The basic idea is to traverse through the complete array and find the value of F(X) for every element of it. The final answer will be the maximum of them.

The steps are as follows:

Create a variable named ‘ANS’ to store the maximum value of F(X) and initialize it with ‘0’.
Traverse through the array ‘ARR’ (let say, iterator be ‘i’ and ‘X’ = ‘ARR[ i ]’).
- Create a variable ‘COUNT’ to count the numbers different from ‘ARR[i]’.
- Run a loop to the array and count the required value to store in ‘COUNT’.
- Store the maximum of ‘ANS’ and ‘COUNT’ in ‘ANS’.
Return ‘ANS’.

Time Complexity

O(N^2), Where ‘N’ is the length of ‘ARR’.

Since we are traversing through the array ‘ARR’ using a nested loop and so, the overall time complexity will be O(N^2).

Space Complexity

O(1)

Since constant extra space is required and so, the overall space complexity will be O(1).

(100% EXP penalty)

Maximum Value of F(x) - VI

Codestudio

Interview problems

Discussion thread on Interview Problem | Maximum Value of F(x) - VI

Hey everyone, creating this thread to discuss the interview problem - Maximum Value of F(x) - VI.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Maximum Value of F(x) - VI

246 views

7 replies

2 upvotes

Console