Ordene una array intercambiando elementos adyacentes de índices que contienen ‘1’ en una string dada

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++ 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 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 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# 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

<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)