Cuente la mediana distinta posible para una array usando rangos dados de elementos

Posted on by Rudeus Greyrat

Dada una array de pares arr[] que denota los rangos de los elementos de una array, la tarea es contar la mediana distinta de cada array posible usando estos rangos.

Ejemplos:  

Entrada: arr[] = {{1, 2}, {2, 3}} 
Salida: 3 
Explicación: 
=> Si x1 = 1 y x2 = 2, la mediana es 1,5 
=> Si x1 = 1 y x2 = 3, la mediana es 2 
=> Si x1 = 2 y x2 = 2, la mediana es 2 
=> Si x1 = 2 y x2 = 3, la mediana es 2,5 
Por lo tanto, el número de medianas distintas es {1,5, 2, 2,5}, es decir, 3

Entrada: arr[] = {{100, 100}, {10, 10000}, {1, 10 9 }} 
Salida: 9991 

Enfoque ingenuo: una solución simple es probar todos los valores posibles de la array y encontrar la mediana de todos esos elementos y contar la mediana distinta de la array. 
Complejidad del tiempo: 

O(k^{N})
 

, donde K son los posibles valores de rango.

Enfoque eficiente: la idea es encontrar la mediana del rango inicial y los rangos finales de los elementos de la array, luego la diferencia de esta mediana denotará la mediana distinta de cada array posible. A continuación se muestra la ilustración del enfoque:

  • Almacene todos los valores del rango inicial en una array. 
    • Ordene la array del rango inicial y encuentre la mediana de la array.
    • Para longitud impar de la array: mediana = A[n/2]
    • Para longitud uniforme de la array – mediana =

\frac{A[n/2] + A[n/2 - 1]}{2}

  • Almacene todos los valores del rango final en una array. 
    • Ordene la array del rango final y encuentre la mediana de la array
    • Para longitud impar de la array, mediana = B[n/2]
    • Para N par , mediana =

\frac{B[n/2] + B[n/2 - 1]}{2}

  • Cuando la longitud de la array es impar, entonces todos los valores integrales difieren en 1 en el rango de la mediana del rango inicial a la mediana del rango final. 
    • Por lo tanto, la cuenta de la mediana distinta será la diferencia de la mediana de los rangos iniciales y la mediana de los rangos finales.
  • Cuando la longitud de la array es par, entonces todos los valores integrales difieren en 0,5, en el rango de la mediana del rango inicial a la mediana del rango final. 
    • Todos los valores que difieren en 0,5 en el rango [l, r] son ​​iguales que todos los valores que difieren en 1 en el rango [2 * l, 2 * r]
    • Por lo tanto, la cuenta de la mediana distinta es

2 * right median - 2 * left median + 1
 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ implementation to Count the
// number of distinct medians of an array
// where each array elements
// are given by a range
 
#include <bits/stdc++.h>
using namespace std;
#define int long long int
 
// Function to Count the
// number of distinct medians of an array
// where each array elements
// are given by a range
void solve(int n,
   const vector<pair<int, int> >& vec)
{
    vector<int> a, b;
 
    // Loop to store the starting
    // and end range in the array
    for (auto pr : vec) {
        a.push_back(pr.first);
        b.push_back(pr.second);
    }
 
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
 
    int left, right, ans;
     
    // Condition to check if the
    // length of the array is odd
    if ((n & 1)) {
        left = a[n / 2];
        right = b[n / 2];
        ans = right - left + 1;
    }
    else {
        left = (a[n / 2] + a[n / 2 - 1]);
        right = (b[n / 2] + b[n / 2 - 1]);
        ans = right - left + 1;
    }
 
    cout << ans << endl;
}
 
// Driver Code
signed main()
{
 
    int N = 3;
    vector<pair<int, int> > vec =
         { { 100, 100 }, { 10, 10000 },
                    { 1, 1000000000 } };
                     
    // Function Call
    solve(N, vec);
 
    return 0;
}

Java

// Java implementation to count the
// number of distinct medians of an
// array where each array elements
// are given by a range
import java.util.*;
import java.awt.*;
 
class GFG{
     
// Function to count the number
// of distinct medians of an array
// where each array elements are
// given by a range
static void solve(int n, ArrayList<Point> vec)
{
    ArrayList<Integer> a = new ArrayList<>();
    ArrayList<Integer> b = new ArrayList<>();
 
    // Loop to store the starting
    // and end range in the array
    for(Point pr : vec)
    {
        a.add(pr.x);
        b.add(pr.y);
    }
 
    Collections.sort(a);
    Collections.sort(b);
 
    int left, right, ans;
 
    // Condition to check if the
    // length of the array is odd
    if ((n & 1) != 0)
    {
        left = a.get(n / 2);
        right = b.get(n / 2);
        ans = right - left + 1;
    }
    else
    {
        left = (a.get(n / 2) +
                a.get(n / 2 - 1));
        right = (b.get(n / 2) +
                 b.get(n / 2 - 1));
        ans = right - left + 1;
    }
    System.out.println(ans);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 3;
     
    ArrayList<Point> vec = new ArrayList<>();
    vec.add(new Point(100, 100));
    vec.add(new Point(10, 10000));
    vec.add(new Point(1, 1000000000));
 
    // Function call
    solve(N, vec);
}
}
 
// This code is contributed by jrishabh99

Python3

# Python3 implementation to count the
# number of distinct medians of an array
# where each array elements
# are given by a range
 
# Function to count the number of 
# distinct medians of an array
# where each array elements
# are given by a range
def solve(n, vec):
 
    a = []
    b = []
 
    # Loop to store the starting
    # and end range in the array
    for pr in vec :
        a.append(pr[0])
        b.append(pr[1])
 
    a.sort()
    b.sort()
     
    # Condition to check if the
    # length of the array is odd
    if ((n & 1)):
        left = a[n // 2]
        right = b[n // 2]
        ans = right - left + 1
     
    else:
        left = (a[n // 2] + a[n // 2 - 1])
        right = (b[n // 2] + b[n // 2 - 1])
        ans = right - left + 1
 
    print(ans)
 
# Driver Code
if __name__ == "__main__":
 
    N = 3
    vec = [ (100, 100), (10, 10000),
            (1, 1000000000) ]
                     
    # Function Call
    solve(N, vec)
 
# This code is contributed by chitranayal

C#

// C# implementation to count the 
// number of distinct medians of
// an array where each array elements 
// are given by a range
using System;
using System.Collections;
using System.Collections.Generic;
 
public class Point
{
    public int x, y;
     
    public Point(int xx, int yy)
    {
        x = xx;
        y = yy;
    }
}
   
class GFG{
 
// Function to count the number
// of distinct medians of an array
// where each array elements are
// given by a range
static void solve(int n, ArrayList vec)
{
    ArrayList a = new ArrayList();
    ArrayList b = new ArrayList();
     
    // Loop to store the starting
    // and end range in the array
    foreach(Point pr in vec)
    {
        a.Add(pr.x);
        b.Add(pr.y);
    }
    a.Sort();
    b.Sort();
  
    int left, right, ans;
     
    // Condition to check if the
    // length of the array is odd
    if ((n & 1) != 0)
    {
        left = (int)a[n / 2];
        right = (int)b[n / 2];
        ans = right - left + 1;
    }
    else
    {
        left = ((int)a[n / 2] +
                (int)a[n / 2 - 1]);
        right = ((int)b[n / 2] +
                 (int)b[n / 2 - 1]);
        ans = right - left + 1;
    }
    Console.WriteLine(ans);
}
 
// Driver code   
static public void Main()
{
    int N = 3;
     
    ArrayList vec = new ArrayList();
    vec.Add(new Point(100, 100));
    vec.Add(new Point(10, 10000));
    vec.Add(new Point(1, 1000000000));
     
    // Function call
    solve(N, vec);
}
}
 
// This code is contributed by offbeat

Javascript

<script>
// Javascript implementation to count the
// number of distinct medians of an
// array where each array elements
// are given by a range
 
// Function to count the number
// of distinct medians of an array
// where each array elements are
// given by a range
function solve(n,vec)
{
    let a = [];
    let b = [];
  
    // Loop to store the starting
    // and end range in the array
    for(let pr=0;pr<vec.length;pr++)
    {
        a.push(vec[pr][0]);
        b.push(vec[pr][1]);
    }
      
    a.sort(function(c,d){return c-d;});
    b.sort(function(c,d){return c-d;});
  
    let left, right, ans;
  
    // Condition to check if the
    // length of the array is odd
    if ((n & 1) != 0)
    {
        left = a[Math.floor(n / 2)];
        right = b[Math.floor(n / 2)];
        ans = right - left + 1;
    }
    else
    {
        left = (a[Math.floor(n / 2)] +
                a[Math.floor(n / 2) - 1]);
        right = (b[Math.floor(n / 2)] +
                 b[Math.floor(n / 2) - 1]);
        ans = right - left + 1;
    }
    document.write(ans);
}
 
// Driver Code
let N = 3;
let vec=[];
vec.push([100,100]);
vec.push([10, 10000]);
vec.push([1, 1000000000]);
 
// Function call
solve(N, vec);
 
 
// This code is contributed by avanitrachhadiya2155
</script>
Producción: 

9991

 

Complejidad de tiempo: O(nlogn), tiempo utilizado para clasificar los vectores ayb
Espacio auxiliar: O(n), ya que el espacio adicional de tamaño n se utiliza para crear vectores.

Publicación traducida automáticamente

Artículo escrito por greenindia y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *