Índice más grande que se alcanzará en Binary Array después de que K salte entre diferentes valores

Dada una array binaria arr[] de tamaño N y un entero K , la tarea es encontrar el índice más alto que se puede alcanzar en exactamente K saltos a partir del primer índice, cuando se puede realizar un salto entre índices que tienen diferentes valores.

Ejemplos:

Entrada: arr[] = {0, 1, 1, 0, 1, 0}, K = 2
Salida: 5
Explicación: Todos los saltos posibles son:
{0, 1, 3}, {0, 2, 3}, { 0, 1, 5}, {0, 2, 5}, {0, 4, 5}
Entonces, el índice más alto que se puede alcanzar es el índice 5.

Entrada: arr[] = {1, 0, 1, 1, 0}, K = 3
Salida: 4

Planteamiento: El problema se puede resolver con base en la siguiente observación:

• El valor más alto posible de K es el mismo que el número total de cambios entre 1 y 0 consecutivos.
• Como en un salto, los dos valores son diferentes, por lo que si K es par, el valor en el índice inicial y el valor en el último índice serán los mismos y si K es diez impares, serán diferentes.
• Ahora, para encontrar el índice más alto (cuando es posible hacer saltos K ), itere desde el final de la array y, en función de que K sea par o impar, devuelva el primer índice i tal que arr[i] = arr[0] o arr[i ] ≠ arr[0] (porque ya se encuentra que entre ellos se pueden hacer un total de K saltos).

A continuación se muestra una ilustración para una mejor comprensión:

Ilustración:

Considere arr[] = {0, 1, 1, 0, 1, 0}, K = 2.

Valor más alto posible de K = 4:
=> 0s consecutivos en el rango [0, 0]. Desplazamientos totales = 0
=> 1s consecutivos en el rango [1, 2]. Cambia de 0s consecutivos a 1s. Desplazamientos totales = 1.
=> 0s consecutivos en el rango [3, 3]. Cambia de 1s consecutivos a 0s. Desplazamientos totales = 1+1 = 2.
=> 1s consecutivos en el rango [4, 4]. Cambia de 0s consecutivos a 1s. Desplazamientos totales = 2+1 = 3.
=> 0s consecutivos en el rango [5, 5]. Cambia de 1s consecutivos a 0s. Turnos totales = 3+1 = 4.

Iterar de i = 5 a 0:
=> Para i = 5 : arr[5] = arr[0] = 0. K = 2, es decir, par. Deja de iterar
El índice más alto que se puede alcanzar es 5.

Una de esas rutas es (0->1->5) .

Siga los pasos que se mencionan a continuación para resolver el problema:

• Atraviesa la array de i = 0 a N-1 :
  • Encuentre cambios totales de 0s consecutivos a 1s consecutivos y viceversa (digamos count ).
• Si K > count , devolver -1 ya que K salta no es posible.
• De lo contrario, atravesar de i = N-1 a 0:
  • Si K es par, detenga la iteración cuando arr[i] = arr[0] .
  • Si K es impar, detenga la iteración cuando arr[i] ≠ arr[0] .
• Devuelve el índice más alto logrado en el paso anterior.

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 find the index to which
// the longest jump can be made
int maxJump(int arr[], int N, int k)
{
    int i;
 
    // To store possible cases count
    int count = 0;
    for (int i = 1; i < N; i++) {
        if (arr[i] != arr[i - 1]) {
            count++;
        }
    }
    if (count >= k) {
 
        // Traversing the array A[]
        // from the end
        // to find longest index
        for (i = N - 1; i >= 0; i--) {
 
            // Firstly checking
            // if k is even and
            // if first and last element
            // match
            if (k % 2 == 0 && arr[i] == arr[0]) {
 
                // Return the required index
                return i;
            }
 
            // Or, if k is odd
            // and first and last
            // element doesn't match
            if (k % 2 != 0 && arr[i] != arr[0]) {
 
                // Return the required index
                return i;
            }
        }
    }
    return -1;
}
 
// Driver Code
int main()
{
    int arr[] = { 0, 1, 1, 0, 1, 0 };
    int N = sizeof(arr) / sizeof(arr[0]);
    int k = 2;
 
    // Function call
    cout << maxJump(arr, N, k);
    return 0;
}

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG {
 
  // Function to find the index to which
  // the longest jump can be made
  static int maxJump(int arr[], int N, int k)
  {
    int i;
 
    // To store possible cases count
    int count = 0;
    for ( i = 1; i < N; i++) {
      if (arr[i] != arr[i - 1]) {
        count++;
      }
    }
    if (count >= k) {
 
      // Traversing the array A[]
      // from the end
      // to find longest index
      for (i = N - 1; i >= 0; i--) {
 
        // Firstly checking
        // if k is even and
        // if first and last element
        // match
        if (k % 2 == 0 && arr[i] == arr[0]) {
 
          // Return the required index
          return i;
        }
 
        // Or, if k is odd
        // and first and last
        // element doesn't match
        if (k % 2 != 0 && arr[i] != arr[0]) {
 
          // Return the required index
          return i;
        }
      }
    }
    return -1;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int arr[] = { 0, 1, 1, 0, 1, 0 };
    int N = arr.length;
    int k = 2;
 
    // Function call
    System.out.println(maxJump(arr, N, k));
  }
}
 
// This code is contributed by lokeshpotta20.

# Python3 Program for the above approach
 
# Function to find the index to which
# the longest jump can be made
def maxJump(arr, N, k):
   
    # To store possible cases count
    count = 0
    for i in range(1, N):
        if arr[i] != arr[i - 1]:
            count += 1
 
    if count >= k:
       
        # Traversing the array A[]
        # from the end
        # to find longest index
        for i in range(N - 1, -1, -1):
           
            # Firstly checking
            # if k is even and
            # if first and last element
            # match
            if k % 2 == 0 and arr[i] == arr[0]:
               
                # Return the required index
                return i
               
            # Or, if k is odd
            # and first and last
            # element doesn't match
            if k % 2 != 0 and arr[i] != arr[0]:
               
                # Return the required index
                return i
    return -1
 
# Driver Code
arr = [0, 1, 1, 0, 1, 0]
N = len(arr)
k = 2
 
# function call
print(maxJump(arr, N, k))
 
# This code is contributed by phasing17.

using System;
 
public class GFG{
 
  // Function to find the index to which
  // the longest jump can be made
  static int maxJump(int[] arr, int N, int k)
  {
    int i;
 
    // To store possible cases count
    int count = 0;
    for ( i = 1; i < N; i++) {
      if (arr[i] != arr[i - 1]) {
        count++;
      }
    }
    if (count >= k) {
 
      // Traversing the array A[]
      // from the end
      // to find longest index
      for (i = N - 1; i >= 0; i--) {
 
        // Firstly checking
        // if k is even and
        // if first and last element
        // match
        if (k % 2 == 0 && arr[i] == arr[0]) {
 
          // Return the required index
          return i;
        }
 
        // Or, if k is odd
        // and first and last
        // element doesn't match
        if (k % 2 != 0 && arr[i] != arr[0]) {
 
          // Return the required index
          return i;
        }
      }
    }
    return -1;
  }
 
  // Driver Code
  static public void Main (){
 
    int[] arr = { 0, 1, 1, 0, 1, 0 };
    int N = arr.Length;
    int k = 2;
 
    // Function call
    Console.Write(maxJump(arr, N, k));
  }
}
 
// This code is contributed by hrithikgarg03188.

<script>
    // JavaScript program for the above approach
 
    // Function to find the index to which
    // the longest jump can be made
    const maxJump = (arr, N, k) => {
        let i;
 
        // To store possible cases count
        let count = 0;
        for (let i = 1; i < N; i++) {
            if (arr[i] != arr[i - 1]) {
                count++;
            }
        }
        if (count >= k) {
 
            // Traversing the array A[]
            // from the end
            // to find longest index
            for (i = N - 1; i >= 0; i--) {
 
                // Firstly checking
                // if k is even and
                // if first and last element
                // match
                if (k % 2 == 0 && arr[i] == arr[0]) {
 
                    // Return the required index
                    return i;
                }
 
                // Or, if k is odd
                // and first and last
                // element doesn't match
                if (k % 2 != 0 && arr[i] != arr[0]) {
 
                    // Return the required index
                    return i;
                }
            }
        }
        return -1;
    }
 
    // Driver Code
 
    let arr = [0, 1, 1, 0, 1, 0];
    let N = arr.length;
    let k = 2;
 
    // Function call
    document.write(maxJump(arr, N, k));
 
// This code is contributed by rakeshsahni
 
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(N)