আমাদের 0 এবং 1 এর একটি বাইনারি ক্রম দেওয়া হয়েছে। এছাড়াও অনুমান করুন একজন ব্যক্তি বর্তমান_পোজে সঞ্চিত একটি অবস্থান বা পয়েন্টে বসে আছেন। এখন বর্তমান_পোস থেকে শুরু করে, যদি বাইনারি সিকোয়েন্সে 0 থাকে তবে এক ধাপ বামে হেমোভ করে ( current_pos - 1)। যদি এটি 1 হয় তবে সে এক ধাপ ডানদিকে সরে যায় (বর্তমান_পোস + 1)। লক্ষ্য হল সম্পূর্ণ বাইনারি সিকোয়েন্স সম্পূর্ণ হওয়ার পরে তিনি যে স্বতন্ত্র অবস্থান বা পয়েন্টগুলি পরিদর্শন করেছেন তা খুঁজে বের করা৷
একটি পয়েন্ট যতবার পরিদর্শন করা হয়েছে তা ব্যবহার করে আমরা এটি সমাধান করব। ফ্রিকোয়েন্সি অ-শূন্য হলে, স্বতন্ত্র বিন্দুর সংখ্যা বাড়ান।
ইনপুট
Path[]= “001100” current_pos=3
আউটপুট
Distinct points visited on number line: 3
ব্যাখ্যা - পথ[0] এবং অবস্থান 3 থেকে শুরু করে।
Path[0]: 0 → move left ...currpos=2 Path[1]: 0 → move left ...currpos=1 Path[2]: 1 → move right ...currpos=2 Path[3]: 1 → move left ...currpos=3 Path[4]: 0 → move left ...currpos=2 Path[5]: 0 → move left ...currpos=1
মোট স্বতন্ত্র অবস্থান হল 3, যা হল 1,2,3
ইনপুট
Path[]= “010101” current_pos=5
আউটপুট
Distinct points visited on number line: 2
ব্যাখ্যা − পাথ[0] এবং অবস্থান 5 থেকে শুরু।
Path[0]: 0 → move left ...currpos=4 Path[1]: 1 → move right ...currpos=5 Path[2]: 0 → move left ...currpos=4 Path[3]: 1 → move right ...currpos=5 Path[4]: 0 → move left ...currpos=4 Path[5]: 1 → move right ...currpos=5
মোট স্বতন্ত্র অবস্থান হল 2, যা হল 4 এবং 5
নিম্নলিখিত প্রোগ্রামে ব্যবহৃত পদ্ধতি
-
0 এবং 1 এর স্ট্রিং পাথে সংরক্ষিত আছে।
-
Current_pos স্টোর স্টার্টিং পয়েন্ট।
-
ফাংশন getDistinctPoints(int current_pos, string path) বর্তমান অবস্থান এবং pathas ইনপুট নেয় এবং স্বতন্ত্র অবস্থান/পয়েন্টের গণনা প্রদান করে।
-
পরিবর্তনশীল লেন্স পথের দৈর্ঘ্য সংরক্ষণ করে।
-
অ্যারে ফ্রিকোয়েন্সি[21] বিন্দুটি কতবার দেখা হয়েছে তার জন্য ফ্রিকোয়েন্সি সংরক্ষণ করতে ব্যবহৃত হয়। সূচক বিন্দু প্রতিনিধিত্ব করে. মোট 0-20।
-
পাথ স্ট্রিং অতিক্রম করা শুরু করুন৷
৷ -
যদি বর্তমান মান 0 হয়, বামে সরান ( current_pos -1 )। এই পয়েন্ট ফ্রিকোয়েন্সির আপডেট ফ্রিকোয়েন্সি[current_pos]++।
-
অন্যথায় বর্তমান মান 1, ডানদিকে সরান ( বর্তমান_পোস +1 )। এই পয়েন্ট ফ্রিকোয়েন্সির আপডেট ফ্রিকোয়েন্সি[current_pos]++।
-
এখন ফ্রিকোয়েন্সি অ্যারে এবং প্রতিটি অ শূন্য মানের জন্য অতিক্রম করুন। সংখ্যা বাড়ান।
-
গণনায় স্বতন্ত্র পরিদর্শিত পয়েন্ট রয়েছে।
- প্রত্যাশিত ফলাফল হিসাবে গণনা করুন।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
//distict points visited between 0 to 20
int getDistinctPoints(int current_pos, string path){
// Length of path
int len = path.length();
int count=0;
// Array to store number of times a point is visited
int frequency[21]={0};
// For all the directions in path
for (int i = 0; i < len; i++) {
//for left direction
if (path[i] == '0') {
current_pos--;
frequency[current_pos]++; //increase visit count
}
// If the direction is right
else {
current_pos++;
frequency[current_pos]++; //increase visit count
}
}
for(int i=0;i<21;i++)
if(frequency[i]!=0) // if visted then frequency[i] is non zero
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
