এই সমস্যায়, আমাদেরকে 1 থেকে N-1 পর্যন্ত মান সম্বলিত N আকারের একটি arr[] দেওয়া হয়েছে এবং একটি মান অ্যারেতে দুবার আসে। আমাদের কাজ হল আকারের একটি সাজানো বিন্যাসে শুধুমাত্র পুনরাবৃত্তিকারী উপাদান খুঁজে পাওয়া .
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
arr[] = {1, 2, 3, 4, 5, 5, 6, 7} আউটপুট
5
সমাধান পদ্ধতি
সমস্যা সমাধানের একটি সহজ পদ্ধতি হল লিনিয়ার সার্চ ব্যবহার করে এবং arr[i] এবং arr[i+1] এর মান একই আছে কিনা তা পরীক্ষা করা। এই ক্ষেত্রে, arr[i] ফেরত দিন যা পুনরাবৃত্তি করা মান।
উদাহরণ 1
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] == arr[i+1])
return (arr[i]);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 4, 5, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
return 0;
} আউটপুট
The repeating value in the array is 4
সমস্যা সমাধানের আরেকটি পদ্ধতি হল একটি বাইনারি অনুসন্ধান অ্যালগরিদম ব্যবহার করে যে উপাদানটি মধ্য সূচকে দুবার ঘটেছে তা খুঁজে বের করা। যদি মাঝের সূচকের মানটি পুনরাবৃত্তি হয় তবে এটি প্রিন্ট করুন। যদি এটি সূচক অবস্থানে না থাকে, তাহলে ডান সাব্যারে অতিক্রম করুন অন্যথায় বাম সাব্যারে অতিক্রম করুন৷
উদাহরণ 2
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
if (s > e)
return -1;
int mid = (s + e) / 2;
if (arr[mid] != mid + 1){
if (mid > 0 && arr[mid]==arr[mid-1])
return arr[mid];
return arr[findRepeatingValueArr(arr, s, mid-1)];
}
return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
return 0;
} আউটপুট
The repeating value in the array is 6
