ISC Practicals and Theory - Array Deduplication

Array deduplication means removing repeated values from an array so that every value appears only once. This program, written in the main method alone, reads an integer array of 1 to 20 elements, builds a new array that keeps the first occurrence of each value in the original order, and prints the new array and its new size. It uses only loops and arrays.

Definition

A value is a duplicate if it has already appeared earlier in the array. Removing duplicates keeps the first occurrence and drops every later one. The remaining elements stay in their original order, and the new size is the number of distinct values.

For example, for 4 7 4 2 7 9 2 4:

• The distinct values, in order of first appearance, are 4, 7, 2, 9.
• The new array is 4 7 2 9 and the new size is 4.

Size constraint: the array size must be from 1 to 20.

Algorithm

1. Read the number of elements n. If it is not from 1 to 20, print an error message and stop.
2. Create the array arr of size n for the input and the array res of size n for the result (it can never need more places than arr). Set m = 0, the number of elements stored in res.
3. Read the n elements into arr.
4. For every element arr[i], set found = false and search the filled part of res (indices 0 to m - 1). If res[j] == arr[i], set found = true and stop searching.
5. If found is still false, the value is new: store it in res[m] and add 1 to m.
6. Print the first m elements of res and the new size m.

Program

The nested loops in main are the whole program: the outer loop takes each element of arr, and the inner loop searches res for it.

import java.util.Scanner;
public class ArrayDeduplication
{
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of elements (1 to 20): ");
        int n = sc.nextInt();                  // number of elements entered by the user (1 to 20)
        if (n < 1 || n > 20)                   // size outside the allowed range
        {
            System.out.println("Invalid input. Size must be from 1 to 20.");
        }
        else
        {
            int[] arr = new int[n];            // original array as entered
            int[] res = new int[n];            // new array holding each value once; it can never need more than n places
            int m = 0;                         // number of elements stored in res (the new size)
            System.out.println("Enter the elements:");
            for (int i = 0; i < n; i++)
            {
                arr[i] = sc.nextInt();
            }
            for (int i = 0; i < n; i++)
            {
                boolean found = false;         // becomes true if arr[i] is already in res
                for (int j = 0; j < m; j++)    // search only the part of res filled so far
                {
                    if (res[j] == arr[i])
                    {
                        found = true;
                        break;
                    }
                }
                if (!found)
                {
                    res[m] = arr[i];           // store the new value
                    m++;                       // one more element in res
                }
            }
            System.out.println("Array after removing duplicates:");
            for (int i = 0; i < m; i++)
            {
                System.out.print(res[i] + " ");
            }
            System.out.println();
            System.out.println("New size = " + m);
        }
    }
}

Variable description table

Sample input and output

Enter the number of elements (1 to 20): 8
Enter the elements:
4 7 4 2 7 9 2 4
Array after removing duplicates:
4 7 2 9 
New size = 4

Enter the number of elements (1 to 20): 4
Enter the elements:
3 -1 0 9
Array after removing duplicates:
3 -1 0 9 
New size = 4

Enter the number of elements (1 to 20): 5
Enter the elements:
6 6 6 6 6
Array after removing duplicates:
6 
New size = 1

Enter the number of elements (1 to 20): 0
Invalid input. Size must be from 1 to 20.

Dry run

Input: n = 8, arr = [4, 7, 4, 2, 7, 9, 2, 4]. At the start m = 0.

The new array is 4 7 2 9 and the new size is 4, which matches the first sample run.

Variations

1. Sorted array "Remove the duplicate elements from a sorted array."
2. Repeated elements "Display only the elements that occur more than once in an array."
3. Frequency count "Display each distinct element of an array with the number of times it occurs."
4. Keep last occurrence "Remove duplicates from an array keeping the last occurrence of each value."