০ থেকে n-1 পর্যন্ত সংখ্যার একটি লিস্ট দেওয়া থাকলে। একটি সংখ্যা যেকোনো সংখ্যকবার রিপিট হতে পারে। এক্সট্রা স্পেস (extra space) না নিয়ে রিপিট হওয়া সংখ্যাগুলো বের করতে হবে। n = 7, লিস্ট [5, 2, 3, 5, 1, 6, 2, 3, 4, 5] হলে উত্তর: 5, 2, 3।
সমাধান: লিস্টের প্রতিটি উপাদান e এর জন্য নিচের ধাপগুলো:
- sign := A[|e|] (e-এর অ্যাবসোলিউট ভ্যালুর ইনডেক্স)
- যদি sign পজিটিভ হয়, তবে নেগেটিভ (negative) করা
- অন্যথায় এটা রিপিটেড (repetition)
উদাহরণ
#include<iostream> #include<cmath> using namespace std; void findDuplicates(int arr[], int size) { for (int i = 0; i < size; i++) { if (arr[abs(arr[i])] >= 0) arr[abs(arr[i])] *= -1; else cout << abs(arr[i]) << " "; } } int main() { int arr[] = {5, 2, 3, 5, 1, 6, 2, 3, 4, 1}; int n = sizeof(arr)/sizeof(arr[0]); findDuplicates(arr, n); } আউটপুট
5 2 3 1
