Dada una array a[] en la que se realizan los siguientes dos tipos de inversiones:
- Recuento de pares de índices (i, j) tales que A[i] > A[j] e i < j
- Recuento de pares de índices (i, j) tales que A[i] > A[j] y j = i + 1
La tarea es comprobar si el recuento de ambas inversiones es igual o no. Si son iguales, escriba “Sí” . De lo contrario, escriba “No” .
Ejemplos:
Entrada: a[] = {1, 0, 2}
Salida: Sí
Explicación:
Cuenta de inversión de Tipo 1 = 1 [(i, j) : (0, 1)]
Cuenta de inversión de Tipo 2 = 1 [(i , j) : (0, 1)]
Entrada: a[] = {1, 2, 0}
Salida: No
Explicación:
Cuenta de inversión de Tipo 1 = 2 [(i, j) : (0, 2);( 1, 2)]
Cuenta de inversión de Tipo 2 = 1 [(i, j) : (1, 2)]
Enfoque:
Para resolver el problema, es necesario entender la diferencia entre las dos inversiones:
- Para el Tipo 2 , si j = 5, entonces solo puedo ser 4 cuando j = i + 1
- Para el Tipo 1, si j = 5 , entonces i puede ser de 0 a 4 , ya que i es menor que j .
- Por lo tanto, la inversión de Tipo 1 es básicamente una inversión de Tipo 2 resumida con todos los pares de índices (i, j) con i que es menor que ( j – 1 ) y a[i] > a[j] .
- Entonces, para cualquier índice j , la tarea es verificar si hay un índice i , que es menor que j – 1 y a[i] > a[j] . Si se encuentra algún par de índices (i, j) , imprima “ No ”. De lo contrario, escriba “ Sí ”.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the // count of inversion of two // types are same or not bool solve(int a[], int n) { int mx = INT_MIN; for (int j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = max(mx, a[j - 1]); } return true; } // Driver code int main() { int a[] = { 1, 0, 2 }; int n = sizeof(a) / sizeof(a[0]); bool possible = solve(a, n); if (possible) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
Java
// Java program to implement // the above approach import java.io.*; class GFG{ // Function to check if the // count of inversion of two // types are same or not static boolean solve(int a[], int n) { int mx = Integer.MIN_VALUE; for(int j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = Math.max(mx, a[j - 1]); } return true; } // Driver code public static void main (String[] args) { int a[] = { 1, 0, 2 }; int n = a.length; boolean possible = solve(a, n); if (possible) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by offbeat
Python3
# Python3 program to implement # the above approach import sys # Function to check if the # count of inversion of two # types are same or not def solve(a, n): mx = -sys.maxsize - 1 for j in range(1, n): # If maximum value is found # to be greater than a[j], # then that pair of indices # (i, j) will add extra value # to inversion of Type 1 if (mx > a[j]): return False # Update max mx = max(mx, a[j - 1]) return True # Driver code a = [ 1, 0, 2 ] n = len(a) possible = solve(a, n) if (possible != 0): print("Yes") else: print("No") # This code is contributed by sanjoy_62
C#
// C# program to implement // the above approach using System; class GFG{ // Function to check if the // count of inversion of two // types are same or not static bool solve(int[] a, int n) { int mx = Int32.MinValue; for(int j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = Math.Max(mx, a[j - 1]); } return true; } // Driver code public static void Main () { int[] a = { 1, 0, 2 }; int n = a.Length; bool possible = solve(a, n); if (possible) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by sanjoy_62
Javascript
<script> // Javascript implementation of the above approach // Function to check if the // count of inversion of two // types are same or not function solve(a, n) { let mx = 0; for(let j = 1; j < n; j++) { // If maximum value is found // to be greater than a[j], // then that pair of indices // (i, j) will add extra value // to inversion of Type 1 if (mx > a[j]) return false; // Update max mx = Math.max(mx, a[j - 1]); } return true; } // Driver Code let a = [ 1, 0, 2 ]; let n = a.length; let possible = solve(a, n); if (possible) document.write("Yes"); else document.write("No"); </script>
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por AyanChowdhury y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA