Categoría: inversion

Número de intercambios para ordenar cuando solo se permite el intercambio adyacente

Posted on by Rudeus Greyrat

Dada una array arr[] de enteros no negativos. Podemos realizar una operación de intercambio en cualquiera de los dos elementos adyacentes de la array. Encuentre la cantidad mínima de intercambios necesarios para ordenar la array en orden ascendente.  Ejemplos:  Input : arr[] = {3, 2, 1} Output : 3 We need to do following swaps … Continue reading «Número de intercambios para ordenar cuando solo se permite el intercambio adyacente»

Expresar una fracción como número natural en módulo ‘m’

Posted on by Rudeus Greyrat

Dados dos enteros A y B donde A no es divisible por B , la tarea es expresar A/B como un número natural módulo m donde m = 1000000007 . Nota: esta representación es útil cuando necesitamos expresar la probabilidad de un evento, el área de curvas y polígonos, etc. Ejemplos:   Entrada: A = 2, B … Continue reading «Expresar una fracción como número natural en módulo ‘m’»

Número de permutaciones con K inversiones

Posted on by Rudeus Greyrat

Dada una array, una inversión se define como un par a[i], a[j] tal que a[i] > a[j] e i < j. Nos dan dos números N y k, necesitamos decir cuántas permutaciones del primer número N tienen exactamente la inversión K. Ejemplos:  Input : N = 3, K = 1 Output : 2 Explanation : … Continue reading «Número de permutaciones con K inversiones»

Voltear horizontalmente una array binaria

Posted on by Rudeus Greyrat

Dada una array binaria. La tarea es voltear la array horizontalmente (encontrar la imagen de la array) y luego invertirla.  Nota :  Voltear una array horizontalmente significa invertir cada fila de la array. Por ejemplo, voltear [1, 1, 0, 0] horizontalmente da como resultado [0, 0, 1, 1]. Invertir una array significa reemplazar cada 0 … Continue reading «Voltear horizontalmente una array binaria»

Contando inversiones en un subarreglo

Posted on by Rudeus Greyrat

Dada una array arr[] , el objetivo es contar el número de inversiones en todas las sub-arrays. Una inversión es un par de índices i y j tales que i > j y arr[i] < arr[j] . Un subarreglo del índice x al y (x<= y) consiste en el elemento arr[x], arr[x+1], …, arr[y] . … Continue reading «Contando inversiones en un subarreglo»

Conteo de pares que violan la propiedad BST

Posted on by Rudeus Greyrat

Dado un árbol binario y una cantidad de Nodes en el árbol, la tarea es encontrar la cantidad de pares que violan la propiedad BST . Binary Search Tree es una estructura de datos de árbol binario basada en Nodes que tiene las siguientes propiedades:  El subárbol izquierdo de un Node contiene solo Nodes con … Continue reading «Conteo de pares que violan la propiedad BST»

Recuento de substrings en una string binaria que contiene más 1 que 0

Posted on by Rudeus Greyrat

Dada una string binaria s , la tarea es calcular el número de tales substrings donde el conteo de 1 es estrictamente mayor que el conteo de 0 .  Ejemplos Entrada: S = “110011” Salida: 11 Explicación: Las  substrings en las que el recuento de 1 es estrictamente mayor que el recuento de 0 son … Continue reading «Recuento de substrings en una string binaria que contiene más 1 que 0»

Cuente pares en una array que contiene i*arr[i] > j*arr[j]

Posted on by Rudeus Greyrat

Dada una array de enteros arr[0..n-1], cuente todos los pares (arr[i], arr[j]) de tal manera que i*arr[i] > j*arr[j], 0 =< yo < j < n. Ejemplos:  Input : arr[] = {5 , 0, 10, 2, 4, 1, 6} Output: 5 Pairs which hold condition i*arr[i] > j*arr[j] are (10, 2) (10, 4) (10, 1) … Continue reading «Cuente pares en una array que contiene i*arr[i] > j*arr[j]»