Generate Array with elements in given range and median as K

• Last Updated : 01 Jul, 2022

Given two integers N and K and a range [L, R], the task is to build an array whose elements are unique and in the range [L, R] and the median of the array is K.

Examples:

Input: N = 6, K = -1, L = -5, R = 5
Output: -4 -3 -2 0 1 2
Explanation: Median = (-2 + 0)/2 = -1 which is equal to K.

Input: N = 5, K = 4, L = 3, R = 8
Output: -1

Approach: The problem can be solved using the following mathematical idea:

• If the array is of odd length the median is the (N/2 + 1)th element after sorting.
• Otherwise, the median will be the average of (N/2) anf (N/2 + 1)th elements.

So the optimal way is to make an array such that the minimum value and the maximum value are as close to the median as possible.

This can be done by simply keeping the difference between the elements as 1.
Therefore the minimum element of the array wll be (K – N/2) and the maximum element will be (K + N/2).

Note: In case of N being even K is the average of two middle elements. So those two elements have a difference of 2 between them and K will not be present in the array.

Follow the steps mentioned below to implement the observation:

• Find the possible minimum and maximum values of the array.
• If either L is greater than the minimum or R is less than the maximum then the array cannot be constructed.
• Otherwise, fix the minimum and generate all the elements by maintaining a gap of 1 between adjacent elements.
• In the case of N being even, the gap between the middle two elements will be 2.
• Return the generated array as the answer.

Below is the implementation of the above approach:

C++

 `// C++ code to implement the above approach` `#include ``using` `namespace` `std;` `// Function to construct the array``vector<``int``> constructArray(``int` `N, ``int` `K, ``int` `L, ``int` `R)``{``    ``vector<``int``> ans;``    ``if` `(L > (K - (N / 2)) || R < (K + (N / 2)))``        ``ans.push_back(-1);``    ``else` `if` `(N & 1)``        ``for` `(``int` `i = K - (N / 2);``             ``i <= K + (N / 2); i++)``            ``ans.push_back(i);``    ``else``        ``for` `(``int` `i = K - (N / 2);``             ``i <= K + (N / 2); i++)``            ``if` `(i != K)``                ``ans.push_back(i);``    ``return` `ans;``}` `// Driver Code``int` `main()``{``    ``int` `N = 6, K = -1;``    ``int` `L = -5, R = 5;` `    ``// Function call``    ``vector<``int``> ans``        ``= constructArray(N, K, L, R);``    ``for` `(``int` `x : ans)``        ``cout << x << ``" "``;``    ``return` `0;``}`

Java

 `// Java code to implement the above approach``import` `java.io.*;``import` `java.util.*;` `class` `GFG {``    ``// Function to construct the array``    ``public` `static` `ArrayList``    ``constructArray(``int` `N, ``int` `K, ``int` `L, ``int` `R)``    ``{``        ``ArrayList ans = ``new` `ArrayList();``        ``if` `(L > (K - (N / ``2``)) || R < (K + (N / ``2``)))``            ``ans.add(-``1``);``        ``else` `if` `((N & ``1``) != ``0``)``            ``for` `(``int` `i = K - (N / ``2``); i <= K + (N / ``2``); i++)``                ``ans.add(i);``        ``else``            ``for` `(``int` `i = K - (N / ``2``); i <= K + (N / ``2``); i++)``                ``if` `(i != K)``                    ``ans.add(i);``        ``return` `ans;``    ``}` `    ``// Driver Code``    ``public` `static` `void` `main(String[] args)``    ``{``        ``int` `N = ``6``, K = -``1``;``        ``int` `L = -``5``, R = ``5``;` `        ``// Function call``        ``ArrayList ans = constructArray(N, K, L, R);``        ``for` `(Integer x : ans)``            ``System.out.print(x + ``" "``);``    ``}``}` `// This code is contributed by Rohit Pradhan`

Python3

 `# Python3 code to implement the above approach` `# Function to construct the array``def` `constructArray(N, K, L, R) :` `    ``ans ``=` `[];``    ``if` `(L > (K ``-` `(N ``/``/` `2``))) ``or` `(R < (K ``+` `(N ``/``/` `2``))) :``        ``ans.append(``-``1``);``    ``elif` `(N & ``1``) :``        ``for` `i ``in` `range``(K``-` `(N``/``/``2``), K ``+` `1` `+` `(N``/``/``2``)) :``            ``ans.append(i);``    ``else` `:``        ``for` `i ``in` `range``(K``-` `(N``/``/``2``), K ``+` `1` `+` `(N``/``/``2``)) :``            ``if` `(i !``=` `K) :``                ``ans.append(i);``                ` `    ``return` `ans;` `# Driver Code``if` `__name__ ``=``=` `"__main__"` `:` `    ``N ``=` `6``; K ``=` `-``1``;``    ``L ``=` `-``5``; R ``=` `5``;` `    ``# Function call``    ``ans ``=` `constructArray(N, K, L, R);``    ``for` `x ``in` `ans:``        ``print``(x,end``=` `" "``);``    ` `    ``# This code is contributed by AnkThon`

C#

 `// C# code to implement the above approach``using` `System;``using` `System.Collections;` `public` `class` `GFG{` `      ``// Function to construct the array``    ``public` `static` `ArrayList constructArray(``int` `N, ``int` `K, ``int` `L, ``int` `R)``    ``{``        ``ArrayList ans = ``new` `ArrayList();``        ``if` `(L > (K - (N / 2)) || R < (K + (N / 2)))``            ``ans.Add(-1);``        ``else` `if` `((N & 1) != 0)``            ``for` `(``int` `i = K - (N / 2); i <= K + (N / 2); i++)``                ``ans.Add(i);``        ``else``            ``for` `(``int` `i = K - (N / 2); i <= K + (N / 2); i++)``                ``if` `(i != K)``                    ``ans.Add(i);``        ``return` `ans;``    ``}` `    ``// Driver Code``    ``static` `public` `void` `Main (){` `        ``int` `N = 6, K = -1;``        ``int` `L = -5, R = 5;` `        ``// Function call``        ``ArrayList ans = constructArray(N, K, L, R);``        ``for` `(``int` `i = 0; i < ans.Count; i++)``            ``Console.Write(ans[i] + ``" "``);``    ``}``}` `// This code is contributed by Dharanendra L V.`

Javascript

 ``

Output

`-4 -3 -2 0 1 2 `

Time Complexity: O(N)
Auxiliary Space: O(N)

My Personal Notes arrow_drop_up
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}