हमें 0 और 1 का बाइनरी क्रम दिया गया है। यह भी मान लें कि कोई व्यक्ति current_pos में संग्रहीत स्थिति या बिंदु पर बैठा है। अब current_pos से शुरू करते हुए, यदि बाइनरी अनुक्रम में 0 है तो एक कदम शेष है ( current_pos - 1)। यदि यह 1 है तो वह एक कदम दाएं (current_pos + 1) चलता है। लक्ष्य पूरे बाइनरी अनुक्रम के पूरा होने के बाद अलग-अलग पदों या बिंदुओं को खोजना है।
हम इसे एक बिंदु पर जाने की संख्या का उपयोग करके हल करेंगे। अगर आवृत्ति शून्य नहीं है, तो अलग-अलग बिंदुओं की संख्या बढ़ाएं।
इनपुट
Path[]= “001100” current_pos=3
आउटपुट
Distinct points visited on number line: 3
स्पष्टीकरण - पथ [0] और स्थिति 3 से शुरू होकर 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 से शुरू होकर 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) वर्तमान स्थिति और पथ इनपुट लेता है और अलग-अलग पदों/बिंदुओं की गिनती देता है।
-
परिवर्तनीय लेन पथ की लंबाई संग्रहीत करता है।
-
ऐरे फ़्रीक्वेंसी [21] का उपयोग फ़्रीक्वेंसी को उस बिंदु पर जितनी बार देखा जाता है, उतनी बार स्टोर करने के लिए किया जाता है। सूचकांक बिंदु का प्रतिनिधित्व करता है। कुल 0-20.
-
पथ स्ट्रिंग को पार करना प्रारंभ करें।
-
यदि वर्तमान मान 0 है, तो बाईं ओर जाएँ ( current_pos -1 )। इस पॉइंटफ़्रीक्वेंसी [current_pos]++ की आवृत्ति अपडेट करें।
-
अन्यथा वर्तमान मान 1 है, दाएं ले जाएं ( current_pos +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