এই সমস্যাতে, আমাদের একটি অ্যারে arr[] দেওয়া আছে যার সাইজ N এবং এতে 1 থেকে N-1 পর্যন্ত মান আছে, কিন্তু একটি মান দুবার আছে। অ্যারেটি সর্টেড। আমাদের কাজ হল সর্টেড অ্যারেতে একমাত্র রিপিটিং এলিমেন্ট বের করা।
উদাহরণ দেখি:
ইনপুট
arr[] = {1, 2, 3, 4, 5, 5, 6, 7}
আউটপুট
5
সমাধানের পদ্ধতি
এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল লিনিয়ার সার্চ ব্যবহার করে arr[i] এবং arr[i+1] একই কিনা চেক করা। যদি একই হয়, তবে arr[i] রিটার্ন করুন।
উদাহরণ ১
#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
আরেকটি দক্ষ পদ্ধতি হল বাইনারি সার্চ অ্যালগরিদম ব্যবহার করা। মিড ইনডেক্সে যেই এলিমেন্ট দুবার আছে সেটি বের করা। যদি মিড ইনডেক্সে না থাকে, তবে রাইট সাবঅ্যারে ট্রাভার্স করুন, অন্যথায় লেফট সাবঅ্যারে।
উদাহরণ ২
#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
