Thread: Removing duplicate elements when merging two arrays

  1. #1
    Registered User
    Join Date
    Feb 2019
    Posts
    7

    Removing duplicate elements when merging two arrays

    I'm having issues trying to figure out how to remove duplicate elements when merging two arrays. The problem I am working on is as follows:

    Write a program that reads in two arrays (a1 and a2) of numbers and creates a new array (a3) of numbers such that the new array contains all the unique numbers of a1 and a2. Assume the input array elements are unique elements. In the main function, ask the user to enter the length of each array, declare and reads in the numbers for each array, and calculate and display the output array.

    Example input/output #1:
    Enter the length of array 1: 5
    Enter the elements of the array: 8 4 1 3 9
    Enter the length of array 2: 3
    Enter the elements of the array: 5 4 8
    Output array: 8 4 1 3 9 5

    Example input/output #2:
    Enter the length of array 1: 4
    Enter the elements of the array: 3 4 1 7
    Enter the length of array 2: 2
    Enter the elements of the array: 6 9
    Output array: 3 4 1 7 6 9

    Here's what I have so far:
    Code:
    #include <stdio.h>
    
    void merge_array(int arr1[], int num1, int arr2[], int num2);
    
    int main(void){
    
        int first_arr[30];
        int second_arr[30];
        int num1, num2;
    
        printf("Enter the length of array 1: ");
        scanf("%d", &num1);
        printf("Enter the elements of the array: ");
        for(int i = 0; i < num1; i++){
            // scan the first array of elements
            scanf("%d", &first_arr[i]);
        }
        
        printf("Enter the length of the array 2: ");
        scanf("%d", &num2);
        printf("Enter the elements of the array: ");
        for(int i = 0; i < num2; i++){
            // scan the second array of elements
            scanf("%d", &second_arr[i]);
        }
        printf("Output array: ");
        merge_array(first_arr, num1, second_arr, num2);
        return 0;
    }
    
    void merge_array(int arr1[], int num1, int arr2[], int num2){
    
        int arr3[60];
        int i, j, k = 0;
    
        for(i = 0; i < num1; i++){
            //copy all the elements from the first array into third array
            arr3[k++] = arr1[i]; 
        }
        for(j = 0; j < num2; j++){
            // copy all the elements from the second array into third array
            arr3[k++] = arr2[j]; 
        }
        for(i = 0; i < (num1 + num2); i++){
            printf("%d ", arr3[i]);
        }
    }
    Any help is greatly appreciated. Thanks!

  2. #2
    Registered User
    Join Date
    May 2009
    Posts
    3,523
    The common solution is to search the third array before inserting values from the second array.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    7
    I tried using an conditional statements to check if an element in the
    second already exists in the first array. The first few test I ran worked fine but the output was backwards... and now when I try to run more test I keep getting at least one duplicate. Is there something wrong with my logic?

    Code:
     #include <stdio.h>
    
    void merge_array(int arr1[], int num1, int arr2[], int num2);
    
    int main(void){
    
        int first_arr[30];
        int second_arr[30];
        int num1, num2;
    
        printf("Enter the length of array 1: ");
        scanf("%d", &num1);
        printf("Enter the elements of the array: ");
        for(int i = 0; i < num1; i++){
            // scan the first array of elements
            scanf("%d", &first_arr[i]);
        }
        
        printf("Enter the length of the array 2: ");
        scanf("%d", &num2);
        printf("Enter the elements of the array: ");
        for(int i = 0; i < num2; i++){
            // scan the second array of elements
            scanf("%d", &second_arr[i]);
        }
        printf("Output array: ");
        merge_array(first_arr, num1, second_arr, num2);
        return 0;
    }
    
    void merge_array(int arr1[], int num1, int arr2[], int num2){
    
        int arr3[60];
        int i, j, k;
        
        // loop through every element in the array
        // and remove any dupilicated elements that 
        // are found in both arrays.
        for(i = 0, j = 0, k = 0; (i < num1) && (j < num2); ){
    
            if(arr1[i] < arr2[j]){
                
                arr3[k] = arr1[i];
                i++;
                k++;
            }
            else if(arr1[i] > arr2[j]){
                
                arr3[k] = arr2[j];
                j++;
                k++;
            }
            else{
    
                arr3[k] = arr1[i];
                i++;
                j++;
                k++;
            }
        }
        if (i < num1){
    
            for(; i < num1; i++){
                //copy all the elements from the first array into third array
                arr3[k] = arr1[i];
                k++;
            }
        }
        else if(j < num2){
            
            for(; j < num2; j++){
                // copy all the elements from the second array into third array
                arr3[k] = arr2[j];
                k++;
            }
        }
        //output the array
        for(i = 0; i < k; i++){
            printf("%d ", arr3[i]);
        }
    }
    The output i get is:
    Removing duplicate elements when merging two arrays-output-png
    Last edited by snoopfrogg; 1 Week Ago at 09:23 PM.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,906
    What happens if you have something like this.
    1 3 5 7 9
    10 8 6 4 2 1

    Somewhere along the line, you need to sort things.

    For me, it's just
    - copy both arrays
    - sort
    - remove duplicates (which will be adjacent after sort).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Feb 2019
    Posts
    7
    Quote Originally Posted by Salem View Post
    What happens if you have something like this.
    1 3 5 7 9
    10 8 6 4 2 1
    This is the output I get
    Removing duplicate elements when merging two arrays-output2-png

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,906
    Well that's not entirely surprising, because your approach is wrong.

    If you want a practical demonstration
    - write all those numbers on small pieces of paper
    - distribute into two piles as shown previously

    Now try to extract numbers from each pile one at a time and figure out what steps you actually perform to ensure you have a unique merged list.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    Feb 2019
    Posts
    7
    I fixed the conditional statements inside the body of my for loop and I got the proper output. I still have some doubt that I might be incorrect even though the output array was correct.

    Here's my code:

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void merge_array(int arr1[], int num1, int arr2[], int num2);
    
    int main(void){
    
        int first_arr[100];
        int second_arr[100];
        int num1, num2;
    
        printf("Enter the length of array 1: ");
        scanf("%d", &num1);
        printf("Enter the elements of the array: ");
        for(int i = 0; i < num1; i++){
            // scan the first array of elements
            scanf("%d", &first_arr[i]);
        }
        
        printf("Enter the length of the array 2: ");
        scanf("%d", &num2);
        printf("Enter the elements of the array: ");
        for(int i = 0; i < num2; i++){
            // scan the second array of elements
            scanf("%d", &second_arr[i]);
        }
        printf("Output array: ");
        merge_array(first_arr, num1, second_arr, num2);
        return 0;
    }
    
    void merge_array(int arr1[], int num1, int arr2[], int num2){
    
        int arr3[200];
        int i, j, k; // k is the count
        
        // loop through every element in the array
        // and remove any dupilicated elements that 
        // are found in both arrays.
        for(i = 0, j = 0, k = 0; (i < num1) && (j < num2); ){
            // check if any elements in arr1 are in arr2
            if(arr1[i] == arr2[j]){
                
                arr3[k] = arr2[j]; // remove the duplicate here?
                j++;
                k++;
            }
            else{
    
                arr3[k] = arr1[i]; // copy elements to arr1
                i++;
                k++;
            }   
        }
        //output the array
        for(i = 0; i < k; i++){
            printf("%d ", arr3[i]);
        }
    EDIT: It isn't working for all outputs...
    Here are some of the test I ran:
    Removing duplicate elements when merging two arrays-output-png
    Last edited by snoopfrogg; 1 Week Ago at 11:00 AM.

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,906
    It didn't work with my test case.
    Code:
    $ ./a.out 
    Enter the length of array 1: 5
    Enter the elements of the array: 1 3 5 7 9
    Enter the length of the array 2: 6
    Enter the elements of the array: 10 8 6 4 2 1
    Output array: 1 3 5 7 9 $
    There's a whole bunch of even numbers missing.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    Feb 2019
    Posts
    7
    Quote Originally Posted by Salem View Post
    It didn't work with my test case.
    Code:
    $ ./a.out 
    Enter the length of array 1: 5
    Enter the elements of the array: 1 3 5 7 9
    Enter the length of the array 2: 6
    Enter the elements of the array: 10 8 6 4 2 1
    Output array: 1 3 5 7 9 $
    There's a whole bunch of even numbers missing.
    That's weird... I ran the test inputs you posted and this the output I got
    Removing duplicate elements when merging two arrays-output2-png

    I'm a bit confused on what I need to do to make it run properly. Do you mind explaining to me what I should do? I'm fairly new to C programming.

  10. #10
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,906
    Have you tried the exercise of trying this using bits of paper?

    You can't write the code until you actually understand the problem.

    Just writing code which copies arrays with some "if" thrown in isn't the way to go.

    > Do you mind explaining to me what I should do?
    I already have.
    Read my posts again.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  11. #11
    Registered User
    Join Date
    May 2009
    Posts
    3,523
    I can not help you with you current code because I do not understand how it could made to work.

    This problem has two clear paths to work on solving.
    1. sort array 1 and 2; then merge the sorted arrays into the third array.
    2. copy array 1 into 2; then scan though array 2 one element at a time; check if element is in array 3. If not, add to array 3.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  12. #12
    Registered User
    Join Date
    Feb 2019
    Posts
    7
    I finally figured it out. I created a search function to make sure I'm not copying any duplicated element into array 3. It searches through the elements in array 3 and inserts elements the elements if they don't exist.

    Thank you for helping me figure it out!

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    void merge_array(int arr1[], int num1, int arr2[], int num2);
    
    int main(void){
    
        int first_arr[100];
        int second_arr[100];
        int num1, num2;
        int i;
    
        printf("Enter the length of array 1: ");
        scanf("%d", &num1);
        printf("Enter the elements of the array: ");
        for(i = 0; i < num1; i++){
            // scan the first array of elements
            scanf("%d", &first_arr[i]);
        }
        
        printf("Enter the length of the array 2: ");
        scanf("%d", &num2);
        printf("Enter the elements of the array: ");
        for(i = 0; i < num2; i++){
            // scan the second array of elements
            scanf("%d", &second_arr[i]);
        }
        printf("Output array: ");
        merge_array(first_arr, num1, second_arr, num2);
        return 0;
    }
    
    // The search function is used to make sure that we dont 
    // copy any duplicate elements into arr3
    int search(int arr3[], int num1, int num2){
    
        int i;
        // loop through the elements in the arr3
        // make sure to avoid copying any 
        // duplicate elements into arr3 
        for(i = 0; i < num1; i++){
            
            if(arr3[i] == num2){
                return i;
            }
        }
        return -1;
    }
    
    // Function used to merge the two arrays into a new array called 
    // arr3 and displays each element, without duplicates
    void merge_array(int arr1[], int num1, int arr2[], int num2){
        
        // contcatinating the elements from arr1 and arr2
        int arr3[num1 + num2];
        int i, k = 0;
        
        // loop through every element in the array
        // and remove any duplicate elements that 
        // are found in both arrays.
        //output the array
        for(i = 0; i < num1; i++){
            // copy the elements from arr1 into arr2
            arr3[k] = arr1[i];
            k++;
        }
        for(i = 0; i < num2; i++){
            // search the elements in arr3
            // if the elements are not present 
            // then insert the element into arr3
            if(search(arr3, num1, arr2[i]) == -1){
                // copy the elements from arr3 into arr3
                arr3[k] = arr2[i];
                k++;
            }
        }
        //output array
        for(i = 0; i < k; i++){
            printf("%d ", arr3[i]);
        }
    }

  13. #13
    Registered User
    Join Date
    May 2009
    Posts
    3,523
    Changing num1 and num2 to size1 and size2 would make your code more readable.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  14. #14
    Registered User
    Join Date
    Feb 2019
    Posts
    7
    Quote Originally Posted by stahta01 View Post
    Changing num1 and num2 to size1 and size2 would make your code more readable.

    Tim S.
    Thanks for the advice.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. removing duplicate elements from an array
    By Pulock2009 in forum C Programming
    Replies: 3
    Last Post: 11-06-2013, 01:25 PM
  2. removing a duplicate entry
    By csharp100 in forum C Programming
    Replies: 4
    Last Post: 04-20-2012, 10:02 AM
  3. Removing duplicate values from std::list
    By Phenom in forum C++ Programming
    Replies: 3
    Last Post: 11-03-2010, 12:59 PM
  4. Removing duplicate items from vector
    By 7heavens in forum C++ Programming
    Replies: 2
    Last Post: 03-08-2010, 05:38 AM

Tags for this Thread