আমাদের একটি বাইনারি সিকোয়েন্স (০ এবং ১) দেওয়া আছে। একটি ব্যক্তি current_pos পজিশনে থাকে। সিকোয়েন্স থেকে ০ পেলে এক ধাপ বামে (current_pos - 1), ১ পেলে এক ধাপ ডানে (current_pos + 1) যাবে। পুরো সিকোয়েন্স শেষ হলে সে কতগুলো ভিন্ন (distinct) পজিশন ভিজিট করেছে তা বের করতে হবে।
এটি ভিজিট ফ্রিকোয়েন্সি দিয়ে সমাধান করা হয়। যদি ফ্রিকোয়েন্সি নন-জিরো হয় তবে ডিস্টিংক্ট পয়েন্ট কাউন্ট বাড়ানো।
ইনপুট
Path[]= "001100" current_pos=3
আউটপুট
Distinct points visited on number line: 3
ব্যাখ্যা: পজিশন ৩ থেকে শুরু করে পাথ অনুসরণ করলে ভিজিট করা পজিশনগুলো: ২, ১, ২, ৩, ২, ১। ডিস্টিংক্ট পজিশন: ১, ২, ৩ (মোট ৩)।
ইনপুট
Path[]= "010101" current_pos=5
আউটপুট
Distinct points visited on number line: 2
ব্যাখ্যা: পজিশন ৫ থেকে শুরু করে পজিশন ৪ এবং ৫ এর মধ্যে অল্টারনেট করে। ডিস্টিংক্ট পজিশন: ৪, ৫ (মোট ২)।
প্রোগ্রামে ব্যবহৃত পদ্ধতি
- ০ এবং ১ স্ট্রিং path-এ স্টোর করা।
- current_pos-এ শুরুর পজিশন স্টোর করা।
- getDistinctPoints(int current_pos, string path) ফাংশন পজিশন ও পাথ নিয়ে ডিস্টিংক্ট পয়েন্ট কাউন্ট রিটার্ন করে।
- frequency[21] অ্যারে দিয়ে প্রতিটি পয়েন্ট কতবার ভিজিট হয়েছে তা স্টোর করা (ইনডেক্স = পয়েন্ট, ০-২০)।
- পাথ ট্র্যাভার্স করলে ০ হলে current_pos--, ১ হলে current_pos++ এবং frequency[current_pos]++ করা।
- frequency অ্যারে ট্র্যাভার্স করে নন-জیرো এন্ট্রি গুনে count বের করা।
- count রিটার্ন করা।
উদাহরণ কোড
#include <bits/stdc++.h>
using namespace std;
int getDistinctPoints(int current_pos, string path){
int len = path.length();
int count = 0;
int frequency[21] = {0};
for (int i = 0; i < len; i++) {
if (path[i] == '0') {
current_pos--;
frequency[current_pos]++;
}
else {
current_pos++;
frequency[current_pos]++;
}
}
for(int i=0; i<21; i++)
if(frequency[i] != 0)
count++;
return count;
}
int main(){
int current_pos = 3;
string path = "011101100";
cout << "Count of distinct points visited on the number line:" << getDistinctPoints(current_pos, path);
return 0;
}আউটপুট
Count of distinct points visited on the number line :5
