Given two arrays A[] and B[] of size N each, the task is to find the number of elements in array B[] that occur before any element that was present before it in array A[].
Example:
Input: N = 5, A[] = {3, 5, 1, 2, 4}, B[] = {4, 3, 1, 5, 2}
Output: 2
Explanation: Array A represent that 3 comes first then followed by 5, 1, 2, 4.
In array B, 4 must comes after 1, 2, 3, 5 but 4 comes before them.
The value 1 is also in invalid order. It comes before 5.Input: N = 3, A[] = {1, 3, 2}, B[] = {2, 1, 3}
Output: 1
Approach: The problem can be solved based on the following idea:
Find the number of elements that are present after all the elements that were present in its prefix in array A[]. Then the remaining elements are the ones that do not follow the rule.
Follow the steps mentioned below to implement the idea:
- Initialize i = 0 and j = 0 to iterate through array A[] and B[] respectively.
- While i and j are both less than N:
- Increment j till B[j] is the same as A[i] or j goes out of the bound of the array size.
- If A[i] and B[j] are the same then B[j] is satisfying the conditions. So increment the count (say C) for this element.
- After the above iteration, increment the value of i to point to the next elements in array A[].
- When the loop ends, return the value of (N-C) as the required answer.
Below is the implementation of the above approach.
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Function to count the number of elements// that occur before any of the element// present in its prefix in array A[]int InvalidOrder(int a[], int b[], int n){ int i = 0, j = 0, temp, validcount = 0; // Loop to count the elements // that are in valid order while (i < n && j < n) { temp = j; while (temp < n && a[i] != b[temp]) { temp++; } if (temp != n) { validcount++; j = temp + 1; } i++; } // Return the answer return (n - validcount);}// Driver codeint main(){ int A[] = { 3, 5, 1, 2, 4 }; int B[] = { 4, 3, 1, 5, 2 }; int N = sizeof(A) / sizeof(A[0]); // Function call cout << InvalidOrder(A, B, N); return 0;} |
Java
// Java code to implement the approachimport java.io.*;class GFG { // Function to count the number of elements // that occur before any of the element // present in its prefix in array A[] static int InvalidOrder(int[] a, int[] b, int n) { int i = 0, j = 0, temp, validcount = 0; // Loop to count the elements // that are in valid order while (i < n && j < n) { temp = j; while (temp < n && a[i] != b[temp]) { temp++; } if (temp != n) { validcount++; j = temp + 1; } i++; } // Return the answer return (n - validcount); } public static void main(String[] args) { int[] A = { 3, 5, 1, 2, 4 }; int[] B = { 4, 3, 1, 5, 2 }; int N = A.length; // Function call System.out.print(InvalidOrder(A, B, N)); }}// This code is contributed by lokeshmvs21. |
Python3
# python3 code to implement the approach# Function to count the number of elements# that occur before any of the element# present in its prefix in array A[]def InvalidOrder(a, b, n): i, j, temp, validcount = 0, 0, 0, 0 # Loop to count the elements # that are in valid order while (i < n and j < n): temp = j while (temp < n and a[i] != b[temp]): temp += 1 if (temp != n): validcount += 1 j = temp + 1 i += 1 # Return the answer return (n - validcount)# Driver codeif __name__ == "__main__": A = [3, 5, 1, 2, 4] B = [4, 3, 1, 5, 2] N = len(A) # Function call print(InvalidOrder(A, B, N)) # This code is contributed by rakeshsahni |
C#
// C# implementationusing System;public class GFG{ static int InvalidOrder(int[] a, int[] b, int n) { int i = 0, j = 0, temp, validcount = 0; // Loop to count the elements // that are in valid order while (i < n && j < n) { temp = j; while (temp < n && a[i] != b[temp]) { temp++; } if (temp != n) { validcount++; j = temp + 1; } i++; } // Return the answer return (n - validcount); } static public void Main (){ int[] A = { 3, 5, 1, 2, 4 }; int[] B = { 4, 3, 1, 5, 2 }; int N = A.Length; // Function call Console.WriteLine(InvalidOrder(A, B, N)); }}// This code is contributed by ksam24000 |
Javascript
<script> // JavaScript code for the above approach // Function to count the number of elements // that occur before any of the element // present in its prefix in array A[] function InvalidOrder(a, b, n) { let i = 0, j = 0, temp, validcount = 0; // Loop to count the elements // that are in valid order while (i < n && j < n) { temp = j; while (temp < n && a[i] != b[temp]) { temp++; } if (temp != n) { validcount++; j = temp + 1; } i++; } // Return the answer return (n - validcount); } // Driver code let A = [3, 5, 1, 2, 4]; let B = [4, 3, 1, 5, 2]; let N = A.length; // Function call document.write(InvalidOrder(A, B, N));// This code is contributed by Potta Lokesh </script> |
Output
2
Time Complexity: O(N)
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!
Share your thoughts in the comments
