Encuentra el complemento relativo de dos arrays ordenadas

Dadas dos arrays ordenadas arr1 y arr2 de tamaño m y n respectivamente. Necesitamos encontrar el complemento relativo de dos arrays, es decir, arr1 – arr2, lo que significa que necesitamos encontrar todos los elementos que están presentes en arr1 pero no en arr2.
Ejemplos: 
 

Input : arr1[] = {3, 6, 10, 12, 15}
        arr2[] = {1, 3, 5, 10, 16}
Output : 6 12 15
The elements 6, 12 and 15 are present
in arr[], but not present in arr2[]
         
Input : arr1[] = {10, 20, 36, 59}
        arr2[] = {5, 10, 15, 59}
Output : 20 36

1. Tome dos punteros i y j que atraviesan arr1 y arr2 respectivamente. 
2. Si el elemento arr1[i] es más pequeño que el elemento arr2[j], imprima este elemento e incremente i. 
3. Si el elemento arr1 es mayor que el elemento arr2[j], entonces incremente j. 
4. De lo contrario, incremente i y j.  

// CPP program to find all those
// elements of arr1[] that are not
// present in arr2[]
#include <iostream>
using namespace std;
 
void relativeComplement(int arr1[], int arr2[],
                               int n, int m) {
 
  int i = 0, j = 0;
  while (i < n && j < m) {
 
    // If current element in arr2[] is
    // greater, then arr1[i] can't be
    // present in arr2[j..m-1]
    if (arr1[i] < arr2[j]) {
      cout << arr1[i] << " ";
      i++;
 
    // Skipping smaller elements of
    // arr2[]
    } else if (arr1[i] > arr2[j]) {
      j++;
 
    // Equal elements found (skipping
    // in both arrays)
    } else if (arr1[i] == arr2[j]) {
      i++;
      j++;
    }
  }
 
  // Printing remaining elements of
  // arr1[]
  while (i < n)
    cout << arr1[i] << " "; 
}
 
// Driver code
int main() {
  int arr1[] = {3, 6, 10, 12, 15};
  int arr2[] = {1, 3, 5, 10, 16};
  int n = sizeof(arr1) / sizeof(arr1[0]);
  int m = sizeof(arr2) / sizeof(arr2[0]);
  relativeComplement(arr1, arr2, n, m);
  return 0;
}

// Java program to find all those
// elements of arr1[] that are not
// present in arr2[]
 
class GFG
{
    static void relativeComplement(int arr1[], int arr2[],
                                             int n, int m)
    {
     
        int i = 0, j = 0;
        while (i < n && j < m)
        {
         
            // If current element in arr2[] is
            // greater, then arr1[i] can't be
            // present in arr2[j..m-1]
            if (arr1[i] < arr2[j])
            {
                System.out.print(arr1[i] + " ");
                i++;
         
            // Skipping smaller elements of
            // arr2[]
            } else if (arr1[i] > arr2[j])
            {
                j++;
         
            // Equal elements found (skipping
            // in both arrays)
            }
            else if (arr1[i] == arr2[j])
            {
                i++;
                j++;
            }
        }
         
        // Printing remaining elements of
        // arr1[]
        while (i < n){
            System.out.print(arr1[i] + " ");
            i++;
        }   
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int arr1[] = {3, 6, 10, 12, 15};
        int arr2[] = {1, 3, 5, 10, 16};
        int n = arr1.length;
        int m = arr2.length;
        relativeComplement(arr1, arr2, n, m);
     }
}
 
// This code is contributed by Anant Agarwal.

# Python program to find all those
# elements of arr1[] that are not
# present in arr2[]
 
def relativeComplement(arr1, arr2, n, m):
  
    i = 0
    j = 0
    while (i < n and j < m):
  
        # If current element in arr2[] is
        # greater, then arr1[i] can't be
        # present in arr2[j..m-1]
        if (arr1[i] < arr2[j]):
            print(arr1[i] , " ", end="")
            i += 1
  
            # Skipping smaller elements of
            # arr2[]
        elif (arr1[i] > arr2[j]):
            j += 1
  
            # Equal elements found (skipping
            # in both arrays)
        elif (arr1[i] == arr2[j]):
            i += 1
            j += 1
     
    # Printing remaining elements of
    # arr1[]
    while (i < n):
        print(arr1[i] , " ", end="")
  
# Driver code
arr1= [3, 6, 10, 12, 15]
arr2 = [1, 3, 5, 10, 16]
n = len(arr1)
m = len(arr2)
relativeComplement(arr1, arr2, n, m)
 
# This code is contributed
# by Anant Agarwal.

// C# program to find all those
// elements of arr1[] that are not
// present in arr2[]
using System;
 
namespace Complement
{
    public class GFG
    {    
                 
        static void relativeComplement(int []arr1, int []arr2,
                                                   int n, int m)
        {
     
        int i = 0, j = 0;
        while (i < n && j < m)
        {
         
            // If current element in arr2[] is
            // greater, then arr1[i] can't be
            // present in arr2[j..m-1]
            if (arr1[i] < arr2[j])
            {
                Console.Write(arr1[i] + " ");
                i++;
         
            // Skipping smaller elements of
            // arr2[]
            } else if (arr1[i] > arr2[j])
            {
                j++;
         
            // Equal elements found (skipping
            // in both arrays)
            }
            else if (arr1[i] == arr2[j])
            {
                i++;
                j++;
            }
        }
         
        // Printing remaining elements of
        // arr1[]
        while (i < n)
            Console.Write(arr1[i] + " ");
    }
     
    // Driver code
    public static void Main()
    {
        int []arr1 = {3, 6, 10, 12, 15};
        int []arr2 = {1, 3, 5, 10, 16};
        int n = arr1.Length;
        int m = arr2.Length;
        relativeComplement(arr1,arr2, n, m);
    }
    }
}
 
// This code is contributed by Sam007

<?php
// PHP program to find all those
// elements of arr1[] that are not
// present in arr2[]
 
function relativeComplement($arr1, $arr2,
                                 $n, $m)
{
 
    $i = 0; $j = 0;
    while ($i < $n && $j < $m)
    {
 
        // If current element in arr2[] is
        // greater, then arr1[i] can't be
        // present in arr2[j..m-1]
        if ($arr1[$i] < $arr2[$j])
        {
            echo $arr1[$i] , " ";
            $i++;
         
            // Skipping smaller elements of
            // arr2[]
        }
        else if ($arr1[$i] > $arr2[$j])
        {
            $j++;
         
            // Equal elements found (skipping
            // in both arrays)
        }
        else if ($arr1[$i] == $arr2[$j])
        {
            $i++;
            $j++;
        }
    }
 
    // Printing remaining elements of
    // arr1[]
    while ($i < $n)
        echo $arr1[$i] , " ";
}
 
// Driver code
{
    $arr1 = array(3, 6, 10, 12, 15);
    $arr2 = array(1, 3, 5, 10, 16);
    $n = sizeof($arr1) / sizeof($arr1[0]);
    $m = sizeof($arr2) / sizeof($arr2[0]);
    relativeComplement($arr1, $arr2, $n, $m);
    return 0;
}
 
// This code is contributed by nitin mittal
?>

<script>
// JavaScript program to find all those
// elements of arr1[] that are not
// present in arr2[]
    function relativeComplement(arr1, arr2,
                                       n, m)
    {
       
        let i = 0, j = 0;
        while (i < n && j < m)
        {
           
            // If current element in arr2[] is
            // greater, then arr1[i] can't be
            // present in arr2[j..m-1]
            if (arr1[i] < arr2[j])
            {
                document.write(arr1[i] + " ");
                i++;
           
            // Skipping smaller elements of
            // arr2[]
            } else if (arr1[i] > arr2[j])
            {
                j++;
           
            // Equal elements found (skipping
            // in both arrays)
            }
            else if (arr1[i] == arr2[j])
            {
                i++;
                j++;
            }
        }
           
        // Printing remaining elements of
        // arr1[]
        while (i < n)
            document.write(arr1[i] + " ");
    }
   
// Driver Code
        let arr1 = [3, 6, 10, 12, 15];
        let arr2 = [1, 3, 5, 10, 16];
        let n = arr1.length;
        let m = arr2.length;
        relativeComplement(arr1, arr2, n, m);
 
// This code is contributed by splevel62.
</script>

Producción : 

6 12 15 

Complejidad del tiempo : O(m + n)

Espacio Auxiliar: O(1)