Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solution
2.1.
Approach
2.2.
Code
3.
Frequently Asked Questions
3.1.
How to find “The minimum number of elements to add to make median equals x?”
3.2.
What is the important condition to check in calculating the answer in the “The minimum number of elements to add to make median equals x” problem?
3.3.
What is the time complexity of the solution for the “The minimum number of elements to add to make median equals x?”
3.4.
How to Find the median of the array given?
3.5.
Is there any other approach to solve “The minimum number of elements to add to make median equals x”?
4.
Conclusion
Last Updated: Mar 27, 2024

The minimum number of elements to add to make median equals x

Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction

For this current problem, we are given an array of elements and a value x. We need to find the minimum number of elements to be added to the array to make the array’s median equal to x. A median is a value that can be calculated using the formula (n+1)/2, where n is the number of elements in the array. That means the Median is the middlemost value of a sorted array.

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

Solution

Approach

Let’s have some simple examples to understand this problem. 

Example1: 

Say, we are provided with an array of elements as a = [3,2,4], x = 2.

So, before adding any element and after sorting the array, the array’s median is three as it is the middlemost value of the array. We can also verify it by using the formula (n+1)/2 = (3+1)/2 = 2, the second element is 3. But we need two as the Median. So by adding 1 to the array, we will get the array as [1,2,3,4]. Now (4+1)/2 = 2. So the second element is two, which is equal to the x value. So here, the minimum number of elements we added is one.

Example2:

Say, we are provided with an array of elements as a = [10, 20, 30], x = 40.

So, before adding any element and after sorting the array, the array’s median is 20 as it is the middlemost value of the array. We can also verify it by using the formula (n+1)/2 = (3+1)/2 = 2, and the second element is 20. But we need 40 as the Median. So first, we check how many elements are less than the value x, equals x, and greater than the value x. So, here all the array elements are less than x, i.e., the number of elements that are less than x is 3. So if we have four more elements (if we add three more elements, then the number of elements will be even, i.e., 6, by using the formula, we will get 30 as the Median), then we can get the Median as of x. Thus by adding 40, 50, 50, and 50 to the array, we can get the array as [10,20,30,40,50,50,50]. Now on checking the formula, we will get the Median as 40.

Here we can observe that, on just checking the array, to find how many elements are greater than x, equal to x, and less than x, we can easily find the minimum number of elements to get added to make the Median equal to x. We can use this approach.
We can have two formulae in this approach:
If the number of elements greater than x is 'g,' the number of elements equal to x is 'e,' and the number of elements less than x is 'l.' Then, 
if 'l' is greater than 'h', then, the answer will be (l - h) + 1 - e; 
And if the value of 'h' is greater than 'l,' then the answer will be (h - l -1) + 1 - e;

In this problem, we just need to print the minimum number of elements to add to make the median equal to x but not to print the elements to be added. So we can follow the below algorithm:

Step1: Initialize the variables l, h, e

Step2: Initiate the loop to traverse through the array once.

Step3: Calculate the ‘l’ value by checking the number of elements less than x.

Step4: Calculate the ‘g’ value by checking the number of elements greater than x.

Step5: Calculate the ‘e’ value by checking the number of elements that equals x.

Step6: Calculate the answer by checking the above given two conditions.

Step7: Finally, return the answer as ans+1-e.

Code

Python:

def Solution(arr, x):

    n = len(arr)

    answer = 0

    #Step1: initialise the variables

    l, g, e = 0, 0, 0

    #Step2: initialise the loop to traverse through the array

    for i in arr:

        if i ==x:  #to calculate the value of 'e'

            e+=1

        elif i > x: #to calculate the value of 'g'

            g+=1

        elif i < x:  #to calculate the value of 'l'

            l+=1

    if l > g:  #Checking the conditions to calculate the answer

        answer = l - g

    elif l < g:

        answer = g - l - 1

    return answer+1-e  #returning the answer.

arr = [10, 20, 30]

x = 40

print(Solution(arr, x))

Output: 

4

The time complexity for this python solution code is O(n).

You can find this solution in different languages by referring to this GFG blog.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How to find “The minimum number of elements to add to make median equals x?”

You can find the minimum number of elements to be added to the array to make the array’s median equal to x by just calculating the number of elements greater than x, less than x, and equal to x.

What is the important condition to check in calculating the answer in the “The minimum number of elements to add to make median equals x” problem?

The main important condition in finding the solution for the “The minimum number of elements to add to make median equals x” problem is if the count of elements that are less than x is greater than the count of elements that are greater than x, we can calculate answer as l-g+1-e, else answer is g-l-e.

What is the time complexity of the solution for the “The minimum number of elements to add to make median equals x?”

The time complexity for the problem “The minimum number of elements to add to make median equals x” is O(n) as we are traversing the whole array at least once for calculating the counting variables.

How to Find the median of the array given?

The Median is the middlemost value of an array after sorting the array in the ascending order. We can find the median of a given array by using the formula (n+1)/2, where n is the number of elements in the array.

Is there any other approach to solve “The minimum number of elements to add to make median equals x”?

There is another approach to solve the problem “The minimum number of elements to add to make median equals x.” The other approach is simple, just to add one more element to the array until the median of the array becomes x. 

Conclusion

This article extensively discussed the problem "The minimum number of elements to add to make median equals x”. We start with a brief introduction, then discuss the problem with some simple examples.

Recommended Readings:

After reading about this problem, are you not feeling excited to read/explore more articles on similar problems? Don't worry; Coding Ninjas has you covered. Refer to our Guided Path on Coding Ninjas Studio to improve yourself in Competitive Programming, Data Structures and Algorithms, JavaScript, System Design, and many more! If you want to test your confidence in coding, you may check out the contests and participate in the mock test series hosted on Coding Ninjas Studio! But suppose you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview bundle, and interview experiences for placement preparations.

Nevertheless, you can consider our paid courses to give your career improvement an edge over others!

Do upvote our blogs and articles if you find them helpful and engaging!

Happy Learning!

 

Previous article
Queries on Left and Right Circular shift on Array
Next article
Given a Sorted and Rotated Array, Find if There is a Pair with a Given Sum
Live masterclass