Dada una array de N enteros distintos. Para cada elemento, la tarea es encontrar el recuento de subsecuencias de todas las subsecuencias posibles cuyo elemento mínimo es el elemento actual.
Ejemplos:
Entrada: arr[] = {1, 2}
Salida: 2 1
Explicación:
Las subsecuencias son {1}, {2}, {1, 2}.
El conteo del elemento más pequeño en cada subsecuencia es:
1 = 2, 2 = 1
Entrada: arr[] = {1, 2, 3}
Salida: 4 2 1
Enfoque ingenuo: la idea es generar todas las subsecuencias posibles de la array dada y contar el elemento más pequeño en cada subsecuencia e imprimir su cuenta para cada elemento de la array.
Complejidad temporal: O(2 N )
Espacio auxiliar: O(N)
Enfoque eficiente: la idea es observar un patrón, es decir, observar que el elemento mínimo ocurre 2 n – 1 veces, el segundo mínimo ocurre 2 n – 2 veces y así sucesivamente… . Por ejemplo:
Sea el arreglo arr[] = {1, 2, 3}
Las subsecuencias son {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}
Mínimo de cada subsecuencia: {1}, {2}, {3}, {1}, {1}, {2}, {1}.
donde
1 ocurre 4 veces, es decir, 2 n – 1 donde n = 3.
2 ocurre 2 veces, es decir, 2 n – 2 donde n = 3.
3 ocurre 1 vez, es decir, 2 n – 3 donde n = 3.
A continuación se muestran los pasos:
- Almacene el índice de cada elemento en un mapa de modo que podamos imprimir el elemento en el orden de la array original.
- Ordenar la array dada.
- Ahora los elementos están en orden creciente y, a partir de la observación anterior, atraviesan la array dada y mantienen el recuento de la subsecuencia de modo que cada elemento sea el elemento más pequeño dado por pow(2, N – 1 – i) .
- Ahora recorra el mapa e imprima el recuento de subsecuencias de acuerdo con el elemento en la array original.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that count the subsequence
// such that each element as the
// minimum element in the subsequence
void solve(int arr[], int N)
{
map<int, int> M;
// Store index in a map
for (int i = 0; i < N; i++) {
M[i] = arr[i];
}
// Sort the array
sort(arr, arr + N);
// To store count of subsequence
unordered_map<int, int> Count;
// Traverse the array
for (int i = 0; i < N; i++) {
// Store count of subsequence
Count[arr[i]] = pow(2, N - i - 1);
}
// Print the count of subsequence
for (auto& it : M) {
cout << Count[M[it.second]] << ' ';
}
}
// Driver code
int main()
{
int arr[] = { 5, 2, 1 };
int N = sizeof arr / sizeof arr[0];
// Function call
solve(arr, N);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function that count the subsequence
// such that each element as the
// minimum element in the subsequence
static void solve(int arr[], int N)
{
HashMap<Integer,
Integer> M = new HashMap<>();
// Store index in a map
for (int i = 0; i < N; i++)
{
M.put(i, arr[i]);
}
// Sort the array
Arrays.sort(arr);
// To store count of subsequence
HashMap<Integer,
Integer> Count = new HashMap<>();
// Traverse the array
for (int i = 0; i < N; i++)
{
// Store count of subsequence
Count.put(arr[i],
(int)Math.pow(2, N - i - 1));
}
// Print the count of subsequence
for (Map.Entry<Integer,
Integer> m : M.entrySet())
{
System.out.print(Count.get(m.getValue()) + " ");
}
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 5, 2, 1 };
int N = arr.length;
// Function call
solve(arr, N);
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach
# Function that count the subsequence
# such that each element as the
# minimum element in the subsequence
def solve(arr, N):
M = {}
# Store index in a map
for i in range(N):
M[i] = arr[i]
# Sort the array
arr.sort()
# To store count of subsequence
Count = {}
# Traverse the array
for i in range(N):
# Store count of subsequence
Count[arr[i]] = pow(2, N - i - 1)
# Print the count of subsequence
for it in Count.values():
print(it, end = " ")
# Driver code
if __name__ == "__main__":
arr = [ 5, 2, 1 ]
N = len(arr)
# Function call
solve(arr, N)
# This code is contributed by chitranayal
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that count the subsequence
// such that each element as the
// minimum element in the subsequence
static void solve(int []arr, int N)
{
Dictionary<int,
int> M = new Dictionary<int,
int>();
// Store index in a map
for (int i = 0; i < N; i++)
{
M.Add(i, arr[i]);
}
// Sort the array
Array.Sort(arr);
// To store count of subsequence
Dictionary<int,
int> Count = new Dictionary<int,
int>();
// Traverse the array
for (int i = 0; i < N; i++)
{
// Store count of subsequence
Count.Add(arr[i],
(int)Math.Pow(2, N - i - 1));
}
// Print the count of subsequence
foreach(KeyValuePair<int, int> m in M)
{
Console.Write(Count[m.Value]);
}
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 5, 2, 1 };
int N = arr.Length;
// Function call
solve(arr, N);
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program for the above approach
// Function that count the subsequence
// such that each element as the
// minimum element in the subsequence
function solve(arr, N)
{
var M = new Map();
// Store index in a map
for (var i = 0; i < N; i++) {
M.set(i, arr[i]);
}
// Sort the array
arr.sort((a,b)=>a-b);
// To store count of subsequence
var Count = new Map();
// Traverse the array
for (var i = 0; i < N; i++) {
// Store count of subsequence
Count.set(arr[i], parseInt(Math.pow(2, N - i - 1)));
}
// Print the count of subsequence
M.forEach((value, key) => {
document.write(Count.get(value) + ' ');
});
}
// Driver code
var arr = [5, 2, 1];
var N = arr.length;
// Function call
solve(arr, N);
// This code is contributed by rrrtnx.
</script>
4 2 1
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA