Dadas dos arrays ordenadas , X[] de tamaño N e Y[] de tamaño M con valores únicos. La tarea es contar el número total de movimientos requeridos entre los arreglos para recorrer todos los elementos en ambos arreglos en orden ascendente si inicialmente, el recorrido comienza desde el arreglo X[] .
Ejemplos:
Entrada: X[] = {1}, Y[] = {2, 3, 4}
Salida: 1
Explicación: Solo se requiere 1 movimiento después de atravesar la array X y luego moverse al índice0 de la array Y y recorrer su resto de los valores.Entrada : X[] = {1, 3, 4}, Y[] = {2, 5, 6}
Salida: 3
Enfoque: El problema dado se puede resolver utilizando la técnica de dos puntos . Siga los pasos a continuación para resolver el problema:
- Inicialice dos punteros, digamos i como 0 y j como 0 apuntando a la array X[] e Y[] respectivamente.
- Inicialice otra variable total_moves como 0 para almacenar el número de movimientos necesarios.
- Dado que el recorrido siempre comienza desde la array X[] , primero compare los valores en el índice actual. Surgen dos casos:
- Si actualmente está presente en la array X[] :
- Si X[i] < Y[j] , simplemente incremente el índice i .
- Si X[i] > Y[j] , incremente total_moves e indexe j .
- Si actualmente está presente en la array Y[] :
- Si Y[j] < X[i] , incrementa el índice j .
- Si Y[j] > X[i] , incremente total_moves e indexe i .
- Repita los pasos anteriores hasta que finalice cualquiera de los recorridos de la array.
- Una vez que finalice el ciclo anterior , total_moves se incrementaría en las siguientes dos condiciones:
- Si el recorrido termina en la array X y j < M , entonces incremente total_moves en 1 .
- Si el recorrido termina en la array Y e i < N , entonces incremente total_moves en 1 .
- Imprime el valor de total_moves como resultado.
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 find the number of moves
// required between the arrays to complete
// the traversal in sorted order
int numberofMoves(int X[], int Y[], int n, int m)
{
// Variable to check if present
// at X array or not
bool present_at_X = true;
// Store total number of moves
int total_moves = 0;
// Initialize i and j pointing to X and
// Y array respectively
int i = 0, j = 0;
// Loop until one array is
// completely traversed
while (i < n && j < m) {
// If currently present at X array,
// and X[i]<Y[j], increment index i
if (present_at_X == true && X[i] < Y[j]) {
i++;
}
// If present at X array and Y[j]<X[i]
else if (present_at_X == true && Y[j] < X[i]) {
// Increment total_moves and update
// present at X variable and index j
total_moves++;
present_at_X = false;
j++;
}
// If present at Y array and
// Y[j] < X[i], increment j
else if (present_at_X == false && Y[j] < X[i]) {
j++;
}
// If present at Y array and
// X[i] < Y[j]
else if (present_at_X == false && X[i] < Y[j]) {
// Increment total_moves and index i
// and update present at X variable
total_moves++;
present_at_X = true;
i++;
}
}
// Check if present at X array and j < m,
// so increment total_moves by 1
if (present_at_X == true && j < m) {
total_moves++;
present_at_X = false;
}
// If finished traversal at Y array
// and X's array traversal is left,
// increment total_moves by 1
if (present_at_X == false && i < n) {
total_moves++;
present_at_X = true;
}
// Return the result
return total_moves;
}
// Driver Code
int main()
{
// Given Input
int X[] = { 1, 3, 4 };
int n = sizeof(X) / sizeof(X[0]);
int Y[] = { 2, 5, 6 };
int m = sizeof(Y) / sizeof(Y[0]);
// Function Call
cout << numberofMoves(X, Y, n, m);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to find the number of moves
// required between the arrays to complete
// the traversal in sorted order
static int numberofMoves(int[] X, int Y[], int n, int m)
{
// Variable to check if present
// at X array or not
boolean present_at_X = true;
// Store total number of moves
int total_moves = 0;
// Initialize i and j pointing to X and
// Y array respectively
int i = 0, j = 0;
// Loop until one array is
// completely traversed
while (i < n && j < m) {
// If currently present at X array,
// and X[i]<Y[j], increment index i
if (present_at_X == true && X[i] < Y[j]) {
i++;
}
// If present at X array and Y[j]<X[i]
else if (present_at_X == true && Y[j] < X[i]) {
// Increment total_moves and update
// present at X variable and index j
total_moves++;
present_at_X = false;
j++;
}
// If present at Y array and
// Y[j] < X[i], increment j
else if (present_at_X == false && Y[j] < X[i]) {
j++;
}
// If present at Y array and
// X[i] < Y[j]
else if (present_at_X == false && X[i] < Y[j]) {
// Increment total_moves and index i
// and update present at X variable
total_moves++;
present_at_X = true;
i++;
}
}
// Check if present at X array and j < m,
// so increment total_moves by 1
if (present_at_X == true && j < m) {
total_moves++;
present_at_X = false;
}
// If finished traversal at Y array
// and X's array traversal is left,
// increment total_moves by 1
if (present_at_X == false && i < n) {
total_moves++;
present_at_X = true;
}
// Return the result
return total_moves;
}
// Driver Code
public static void main(String[] args)
{
// Given Input
int X[] = { 1, 3, 4 };
int n = X.length;
int Y[] = { 2, 5, 6 };
int m = Y.length;
// Function Call
System.out.print(numberofMoves(X, Y, n, m));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python3 program for the above approach # Function to find the number of moves # required between the arrays to complete # the traversal in sorted order def numberofMoves(X, Y, n, m): # Variable to check if present # at X array or not present_at_X = True # Store total number of moves total_moves = 0 # Initialize i and j pointing to X and # Y array respectively i, j = 0, 0 # Loop until one array is # completely traversed while (i < n and j < m): # If currently present at X array, # and X[i]<Y[j], increment index i if (present_at_X == True and X[i] < Y[j]): i += 1 # If present at X array and Y[j]<X[i] elif (present_at_X == True and Y[j] < X[i]): # Increment total_moves and update # present at X variable and index j total_moves += 1 present_at_X = False j += 1 # If present at Y array and # Y[j] < X[i], increment j elif (present_at_X == False and Y[j] < X[i]): j += 1 # If present at Y array and # X[i] < Y[j] elif (present_at_X == False and X[i] < Y[j]): # Increment total_moves and index i # and update present at X variable total_moves += 1 present_at_X = True i += 1 # Check if present at X array and j < m, # so increment total_moves by 1 if (present_at_X == True and j < m): total_moves += 1 present_at_X = False # If finished traversal at Y array # and X's array traversal is left, # increment total_moves by 1 if (present_at_X == False and i < n): total_moves += 1 present_at_X = True # Return the result return total_moves # Driver Code if __name__ == '__main__': # Given Input X = [ 1, 3, 4 ] n = len(X) Y = [ 2, 5, 6 ] m = len(Y) # Function Call print(numberofMoves(X, Y, n, m)) # This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
public class GFG{
// Function to find the number of moves
// required between the arrays to complete
// the traversal in sorted order
static int numberofMoves(int[] X, int[] Y, int n, int m)
{
// Variable to check if present
// at X array or not
bool present_at_X = true;
// Store total number of moves
int total_moves = 0;
// Initialize i and j pointing to X and
// Y array respectively
int i = 0, j = 0;
// Loop until one array is
// completely traversed
while (i < n && j < m) {
// If currently present at X array,
// and X[i]<Y[j], increment index i
if (present_at_X == true && X[i] < Y[j]) {
i++;
}
// If present at X array and Y[j]<X[i]
else if (present_at_X == true && Y[j] < X[i]) {
// Increment total_moves and update
// present at X variable and index j
total_moves++;
present_at_X = false;
j++;
}
// If present at Y array and
// Y[j] < X[i], increment j
else if (present_at_X == false && Y[j] < X[i]) {
j++;
}
// If present at Y array and
// X[i] < Y[j]
else if (present_at_X == false && X[i] < Y[j]) {
// Increment total_moves and index i
// and update present at X variable
total_moves++;
present_at_X = true;
i++;
}
}
// Check if present at X array and j < m,
// so increment total_moves by 1
if (present_at_X == true && j < m) {
total_moves++;
present_at_X = false;
}
// If finished traversal at Y array
// and X's array traversal is left,
// increment total_moves by 1
if (present_at_X == false && i < n) {
total_moves++;
present_at_X = true;
}
// Return the result
return total_moves;
}
// Driver Code
static public void Main ()
{
// Given Input
int[] X = { 1, 3, 4 };
int n = X.Length;
int[] Y = { 2, 5, 6 };
int m = Y.Length;
// Function Call
Console.WriteLine(numberofMoves(X, Y, n, m));
}
}
// This code is contributed by unknown2108.
Javascript
<script>
// JavaScript program for the above approach
// Function to find the number of moves
// required between the arrays to complete
// the traversal in sorted order
function numberofMoves(X,Y,n,m)
{
// Variable to check if present
// at X array or not
let present_at_X = true;
// Store total number of moves
let total_moves = 0;
// Initialize i and j pointing to X and
// Y array respectively
let i = 0, j = 0;
// Loop until one array is
// completely traversed
while (i < n && j < m) {
// If currently present at X array,
// and X[i]<Y[j], increment index i
if (present_at_X == true && X[i] < Y[j]) {
i++;
}
// If present at X array and Y[j]<X[i]
else if (present_at_X == true && Y[j] < X[i]) {
// Increment total_moves and update
// present at X variable and index j
total_moves++;
present_at_X = false;
j++;
}
// If present at Y array and
// Y[j] < X[i], increment j
else if (present_at_X == false && Y[j] < X[i]) {
j++;
}
// If present at Y array and
// X[i] < Y[j]
else if (present_at_X == false && X[i] < Y[j]) {
// Increment total_moves and index i
// and update present at X variable
total_moves++;
present_at_X = true;
i++;
}
}
// Check if present at X array and j < m,
// so increment total_moves by 1
if (present_at_X == true && j < m) {
total_moves++;
present_at_X = false;
}
// If finished traversal at Y array
// and X's array traversal is left,
// increment total_moves by 1
if (present_at_X == false && i < n) {
total_moves++;
present_at_X = true;
}
// Return the result
return total_moves;
}
// Driver Code
// Given Input
var X = [1, 3, 4 ];
var n =X.length;
var Y = [2, 5, 6 ];
var m = Y.length;
// Function Call
document.write(numberofMoves(X, Y, n, m));
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N+M)
Espacio auxiliar: O(1)