Remove Duplicates in an Arithmetic Progression (AP) Series

Given an arithmetic progression and having any number of duplicates, we have to find the index of first occurrence of duplicate element in the series. After getting the index we will remove the duplicates from the series and thus will provide the usual AP series.

Note: All duplicates will be adjacent.

Examples:

Input : arr[] = {2,4,6,6,6,8,10};
        Common difference  = 2
Output : 2, After removal of Duplicates arr[] = {2,4,6,8,10,12,14};
It will return true 2 as at this comes 6, and 6 is the repeated number

Input : arr[] = {5,8,11,14,14,17,20};
        Common difference = 3
Output : 3, After removal of Duplicates arr[] = {5,8,11,14,17,20,23};
It will return true 3 as at this comes 14, and 14 is the repeated number

Approach:
We will store the frequency of duplicated elements in hash and then as the minimum occurrence of duplicated element would be 2, we will get the first element which is duplicated in the series and thus check for its index. After getting an index the series will be updated with common difference*c where c is the remaining elements after the first duplicated element in the series.

Below is the Java implementation of above approach

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class JavaProgram {
    public static int findIndex(int arr[], int n) {
        // Insert all elements in a map with the frequency of duplicated elements
        Map<Integer, Integer> hm = new HashMap<>();

        for (int i = 0; i < n; i++) {
            int key = arr[i];
            if (hm.containsKey(key)) {
                int freq = hm.get(key);
                freq++;
                hm.put(key, freq);
            } else
                hm.put(key, 1);
        }

        // Minimum occurrence of any duplicated element would be 2
        int minVal = 2;
        int res = 0;
        for (Entry<Integer, Integer> entry : hm.entrySet()) {
            if (minVal <= entry.getValue()) {
                res = entry.getKey();
                break;
            }
        }

        // To get the index of the first duplicated element
        int ind = -1;
        for (int i = 0; i < n; i++) {
            if (arr[i] == res) {
                ind = i;
                break;
            }
        }

        return ind;
    }

    // Updating the series
    public static void removeDuplicate(int arr[], int ind, int count, int cd) {
        int c = 1;
        for (int i = ind + 1; i < arr.length && c <= count; i++, c++)
            arr[i] = arr[ind] + c * cd;

        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }

    // Driver code
    public static void main(String[] args) {
        int arr[] = {2, 4, 4, 6, 6, 6, 8, 8, 8, 8, 10, 10, 12, 14, 16, 18, 20, 22, 24, 26};
        int len = arr.length;
        int ind = findIndex(arr, len);
        System.out.println("First Duplicate at: " + ind);
        removeDuplicate(arr, ind, len - 1 - ind, 2);
    }
}

Output:

First Duplicate at: 1
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40

Time Complexity:

In findIndex, you loop through the input array, taking O(n).
You loop through the frequency map to find duplicates, also O(n).
Finding the index of the first duplicate takes O(n) as well.
Overall time complexity is O(n).

Space Complexity:

A HashMap (hm) stores frequencies, taking O(n) in the worst case.
Few int variables (minVal, res, ind, c) have O(1) space.
Overall space complexity is O(n) due to the HashMap.

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.