Given two positive integers N and X. The task is to print the maximum median possible by generating an Array of size N with sum X
Examples:
Input: N = 1, X = 7
Output: 7
Explanation: Array can be: [7], median is the 1st element, i.e., 7.Input: N = 7, X = 18
Output: 4
Explanation: One of the possible arrays can be: [0, 1, 2, 3, 4, 4, 4]. The median = ceil(n/2)th element = ceil(7/2) = 5th element, i.e., 4.
Approach: Consider that the median needs to be maximized so the greedy approach can be to make all the elements before the position of the median element as zero and equally divide the sum X among the rest of the elements.
Follow the below steps to solve the problem:
- If n = 1, print X.
- For n >= 2.
- Create a variable median_pos = ceil((double)(n)/2.0).
- Decrement median_pos, as to represent the index value.
- Create a variable median = X/(n-median_pos).
- Print median.
Below is the implementation for the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum median possibleint maximizeMedian(int n, int X){ // If only 1 element present if (n == 1) { return X; } else { // Position of median int median_pos = ceil((double)(n) / (2.0)); median_pos--; int median = X / (n - median_pos); return median; } return 0;}// Driver Codeint main(){ int n = 1, X = 7; cout << maximizeMedian(n, X);} |
Java
// Java program for the above approachimport java.util.*;public class GFG { // Function to find the maximum median possible static int maximizeMedian(int n, int X) { // If only 1 element present if (n == 1) { return X; } else { // Position of median int median_pos = (int)Math.ceil((double)(n) / (2.0)); median_pos--; int median = X / (n - median_pos); return median; } } // Driver Code public static void main(String args[]) { int n = 1, X = 7; System.out.println(maximizeMedian(n, X)); }}// This code is contributed by Samim Hossain Mondal. |
Python3
# Python code for the above approach# Function to find the maximum median possibledef maximizeMedian(n, X): # If only 1 element present if (n == 1): return X else: # Position of median median_pos = (n) // (2.0) median_pos -= 1 median = X // (n - median_pos) return median return 0# Driver Coden = 1X = 7print(maximizeMedian(n, X))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;class GFG { // Function to find the maximum median possible static int maximizeMedian(int n, int X) { // If only 1 element present if (n == 1) { return X; } else { // Position of median int median_pos = (int)Math.Ceiling((double)(n) / (2.0)); median_pos--; int median = X / (n - median_pos); return median; } } // Driver Code public static void Main() { int n = 1, X = 7; Console.WriteLine(maximizeMedian(n, X)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to find the maximum median possible function maximizeMedian(n, X) { // If only 1 element present if (n == 1) { return X; } else { // Position of median let median_pos = Math.ceil((n) / (2.0)); median_pos--; let median = X / (n - median_pos); return median; } return 0; } // Driver Code let n = 1, X = 7; document.write(maximizeMedian(n, X)); // This code is contributed by Potta Lokesh </script> |
7
Time Complexity: O(1)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
