Dada una array arr[] de tamaño N y una string binaria S , la tarea es verificar si es posible ordenar la array arr[] intercambiando elementos de array adyacentes, digamos arr[i] y arr[i + 1] si S[i] es igual a ‘1’. Si es posible, escriba «Sí». De lo contrario, escriba “No” .
Ejemplos:
Entrada: N = 6, arr[] = {2, 5, 3, 4, 6}, S = “01110”
Salida: Sí
Explicación:
Los índices que se pueden intercambiar son {1, 2, 3}.
Intercambiar arr[1] y arr[2] modifica la array arr[] a {1, 2, 3, 5, 4, 6}.
Intercambiar arr[3] y arr[4] modifica la array arr[] a {1, 2, 3, 4, 5, 6}.Entrada: N = 6, arr[] = {1, 2, 5, 3, 4, 6}, S = “01010”
Salida: No
Enfoque: Eche un vistazo a algún par (i, j) en la array arr[] tal que i < j y initial arr[i] > arr[j] . Eso significa que se deben permitir todos los intercambios de i a j – 1 . Entonces es fácil notar que es suficiente verificar solo i e i + 1 ya que cualquier otro par puede deducirse de esto. Siga los pasos a continuación para resolver el problema:
- Iterar sobre el rango [0, N – 1] y realizar los siguientes pasos:
- Si S[i] es ‘1’, entonces inicialice una variable, digamos j, como igual a i.
- Iterar sobre el rango hasta que s[j] sea igual a ‘ 1 ′ y j sea menor que la longitud de la string s . Aumente el valor de j en 1 .
- Ordene el subarreglo en el arreglo arr[] de i a j+1.
- Iterar sobre el rango [0, N – 2] y realizar los siguientes pasos:
- Si el valor de arr[i] es mayor que arr[i + 1], imprima No , rompa el bucle y regrese.
- Imprima Sí ya que la array se ordena intercambiando los índices permitidos.
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 to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s void checkIfPossibleToSort(int n, int arr[], string s) { // Sort the parts of array // where swaps are allowed for (int i = 0; i < n - 1; i++) { if (s[i] == '1') { int j = i; // Iterate over the range // till s[j] is equal to '1' while (s[j] == '1') { j++; } // Sort the subarray sort(arr + i, arr + j + 1); i = j; } } // Check if the array remains unsorted for (int i = 0; i < n - 1; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { printf("No\n"); return; } } printf("Yes\n"); } // Driver Code int main() { // Given Input int n = 6; int arr[] = { 2, 5, 3, 4, 6 }; string s = "01110"; // Function Call checkIfPossibleToSort(n, arr, s); return 0; }
Java
// Java program for the above approach import java.util.Arrays; class GFG{ // Function to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s public static void checkIfPossibleToSort(int n, int arr[], String s) { // Sort the parts of array // where swaps are allowed for(int i = 0; i < n - 1; i++) { if (s.charAt(i) == '1') { int j = i; // Iterate over the range // till s[j] is equal to '1' while (s.charAt(j) == '1') { j++; } // Sort the subarray Arrays.sort(arr, i, j); i = j; } } // Check if the array remains unsorted for(int i = 0; i < n - 2; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { System.out.println("No"); return; } } System.out.println("Yes"); } // Driver Code public static void main(String args[]) { // Given Input int n = 6; int arr[] = { 2, 5, 3, 4, 6 }; String s = "01110"; // Function Call checkIfPossibleToSort(n, arr, s); } } // This code is contributed by gfgking
Python3
# Python3 program for the above approach # Function to check if it is possible # to sort the array arr[] by swapping # array elements from indices containing # adjacent pairs of 1s in the string s def checkIfPossibleToSort(n, arr, s): # Sort the parts of array # where swaps are allowed for i in range(n-1): if s[i] == '1': j = i # Iterate over the range # till s[j] is equal to '1' while s[j] == '1': j += 1 # sort the array arr = arr[:i] + sorted(arr[i:j+1]) + arr[j+1:] i = j # Check if the array remains unsorted for i in range(n-2): # If found to be true, then it is # not possible to sort the array if arr[i] > arr[i+1]: print("No") return print("Yes") # Driver code # Given input n = 6 arr = [2, 5, 3, 4, 6] s = "01110" # function call checkIfPossibleToSort(n, arr, s) # This code is contributed by Parth Manchanda
C#
// C# program for the above approach using System; class GFG{ // Function to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s public static void checkIfPossibleToSort(int n, int []arr, String s) { // Sort the parts of array // where swaps are allowed for(int i = 0; i < n - 1; i++) { if (s[i] == '1') { int j = i; // Iterate over the range // till s[j] is equal to '1' while (s[j] == '1') { j++; } // Sort the subarray Array.Sort(arr, i, j); i = j; } } // Check if the array remains unsorted for(int i = 0; i < n - 2; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { Console.Write("No"); return; } } Console.Write("Yes"); } // Driver Code public static void Main(String []args) { // Given Input int n = 6; int []arr = { 2, 5, 3, 4, 6 }; String s = "01110"; // Function Call checkIfPossibleToSort(n, arr, s); } } // This code is contributed by shivanisinghss2110
Javascript
<script> // Javascript program for the above approach // Function to check if it is possible // to sort the array arr[] by swapping // array elements from indices containing // adjacent pairs of 1s in the string s function checkIfPossibleToSort(n, arr, s) { // Sort the parts of array // where swaps are allowed for (let i = 0; i < n - 1; i++) { if (s[i] == "1") { let j = i; // Iterate over the range // till s[j] is equal to '1' while (s[j] == "1") { j++; } // Sort the subarray arr = [ ...arr.slice(0, i), ...arr.slice(i, j + 1).sort((a, b) => a - b), ...arr.slice(j + 1, arr.length - 1), ]; i = j; } } // Check if the array remains unsorted for (let i = 0; i < n - 1; i++) { // If found to be true, then it is // not possible to sort the array if (arr[i] > arr[i + 1]) { document.write("No<br>"); return; } } document.write("Yes\n"); } // Driver Code // Given Input let n = 6; let arr = [2, 5, 3, 4, 6]; let s = "01110"; // Function Call checkIfPossibleToSort(n, arr, s); // tHIS CODE IS CONTRIBUTED BY _SAURABH_JAISWAL. </script>
Yes
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA