সি প্রোগ্রাম দিয়ে অ্যারে থেকে ডুপ্লিকেট এলিমেন্ট ডিলিট করা

ডুপ্লিকেট এলিমেন্ট মুছে অ্যারে ইউনিক করা

অ্যারে থেকে ডুপ্লিকেট মানগুলো মুছে ফেলা হয় যাতে প্রতিটি এলিমেন্ট একবারই থাকে। অ্যারেতে শিফটিং (shifting) দিয়ে ডুপ্লিকেট মুছে দেওয়া হয়।

অ্যালগরিদম

1. বহিরের লুপ: i = 0 থেকে n-1 পর্যন্ত।
2. ভিতরের লুপ: j = i+1 থেকে n-1 পর্যন্ত।
3. যদি a[i] == a[j] হয়:
   • j থেকে শেষ পর্যন্ত সব এলিমেন্ট একপাশ বামে শিফট করুন (a[k] = a[k+1])
   • j-- (নতুন এলিমেন্ট চেক করার জন্য)
   • n-- (অ্যারে সাইজ কমান)

সি প্রোগ্রাম

#include <stdio.h>
#include <stdlib.h>

int main() {
    int a[50], i, j, k, n;

    printf("Enter array size: ");
    scanf("%d", &n);

    printf("Enter %d elements: ", n);
    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    printf("Original array: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");

    // Remove duplicates
    for (i = 0; i < n; i++) {
        for (j = i+1; j < n; j++) {
            if (a[i] == a[j]) {
                // Shift left
                for (k = j; k < n-1; k++)
                    a[k] = a[k+1];
                n--;   // সাইজ কমান
                j--;   // একই ইন্ডেক্স রিচেক
            }
        }
    }

    printf("After removing duplicates: ");
    for (i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");

    return 0;
}

আউটপুট

Enter array size: 10
Enter 10 elements: 1 1 2 4 3 5 6 5 7 1
Original array: 1 1 2 4 3 5 6 5 7 1
After removing duplicates: 1 2 4 3 5 6 7

টাইম কমপ্লেক্সিটি

• ওয়ার্স্ট কেস: O(n²) (নেস্টেড লুপ + শিফটিং)
• স্পেস: O(1) এক্সট্রা (ইন-প্লেস)

দ্রুত পদ্ধতি (সর্টেড অ্যারে হলে)

যদি অ্যারে সর্টেড থাকে, ডুপ্লিকেট মুছে ফেলা O(n)-এ সম্ভব:

int j = 0;
for (int i = 1; i < n; i++)
    if (a[i] != a[j])
        a[++j] = a[i];
n = j + 1;

অ্যারে সর্টেড না থাকলে (O(n log n))

1. অ্যারে সর্ট করুন (qsort)।
2. উপরের O(n) পদ্ধতিতে ডুপ্লিকেট মুছুন।