Given two sorted arrays, X[] of size N and Y[] of size M having unique values. The task is to count the total number of moves required between the arrays to traverse all the elements in both the arrays in ascending order if initially, the traversal starts from the X[] array.
Examples:
Input: X[] = {1}, Y[] = {2, 3, 4}
Output: 1
Explanation: Only 1 move is required after traversing the X array and then move to the 0 index of the Y array and traverse its rest of the values.Input: X[] = {1, 3, 4}, Y[] = {2, 5, 6}
Output: 3
Approach: The given problem can be solved using the two-pointer technique. Follow the below steps to solve the problem:
- Initialize two pointers, say i as 0 and j as 0 pointing to the X[] and Y[] array respectively.
- Initialize another variable total_moves as 0 to store the number of moves required.
- Since traversal always starts from the X[] array, so first compare the values at the current index. There arise two cases:
- If currently present at X[] array:
- If X[i] < Y[j], just increment index i.
- If X[i] > Y[j], increment total_moves and index j.
- If currently present at Y[] array:
- If Y[j] < X[i], increment index j.
- If Y[j] > X[i], increment total_moves and index i.
- Repeat the above steps until any one of the array traversals is finished.
- Once the above loop finishes, total_moves would be incremented in the following two conditions:
- If traversal finishes at X array and j < M, then increment total_moves by 1.
- If traversal finishes at Y array and i < N, then increment total_moves by 1.
- Print the value of total_moves as the result.
Below is the implementation of the above approach:
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 orderint 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 Codeint 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 approachimport java.util.*;class GFG{ // Function to find the number of moves// required between the arrays to complete// the traversal in sorted orderstatic 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 Codepublic 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 orderdef 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 Codeif __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 approachusing System;public class GFG{ // Function to find the number of moves// required between the arrays to complete// the traversal in sorted orderstatic 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 orderfunction 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> |
Output
3
Time Complexity: O(N+M)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
