Gray Code

-

আজকের প্রব্লেম এর নাম হচ্ছে গ্রে কোড (Gray Code) । এটা LeetCode  এর একটা প্রব্লেম

প্রব্লেমঃ তোমাকে একটা সংখ্যা N  দেয়া আছে। তোমাকে একটা সিকুয়েন্স বানাতে হবে যেখানে

১ । সিকুয়েন্স এর প্রত্যেক্টা সংখ্যা ০ থেকে (২^N)  - ১   এর মধ্যে হতে হবে। 

২। সিকুয়েন্স এর প্রথম সংখ্যাটা ০ হবে।

৩। সিকুয়েন্স এর প্রত্যেকটা সংখ্যা ভিন্ন হতে হবে।

৪। পাশাপাশি যেকোন দুইটা সংখ্যার বাইনারি রিপ্রেজেন্টেশন এর পার্থক্য এক্সাক্টলি একটা বিটে হতে হবে।

৫। প্রথম ও শেষ সংখ্যার বাইনারি রিপ্রেজেন্টেশন এর পার্থক্য এক্সাক্টলি একটা বিটে হতে হবে।

সলিউশনঃ

এটার সলিউশন খুব ই সহজ যদি বাইনারি কোড থেকে কিভাবে  গ্রে কোড এ কনভার্ট করা যায় সেটা আগে থেকে জানা যায়।
ধরি ৫ কে গ্রে কোড এ কনভার্ট করবো।
৪ এর বাইনারি ১০০
বিটগুলোকে বাম থেকে যদি নাম্বারিং করি তাহলে দাঁড়ায় 

বাইনারিঃ   ১   ০   ০
নাম্বারিংঃ   ১   ২   ৩

প্রথমে সবচেয়ে বামের বিট অর্থাৎ ১ নম্বর বিট হুবুহু লিখবো।  এখন পর্যন্ত তাহলে গ্রে কোডঃ ১

এরপর ১ম ও ২য় বিট এর BITWISE XOR করলে যা হবে সেটা গ্রে কোড ২য় বিট। গ্রে কোডঃ ১ ১(১ XOR ০ = ১)

এরপর ২য় ও ৩য় বিট এর BITWISE XOR করলে যা হবে সেটা গ্রে কোড ৩য় বিট। এখন পর্যন্ত 
গ্রে কোডঃ ১ ১ ০(০ XOR ০ = ০)

সুতরাং গ্রে কোড হলো ১১০ যা দশমিকে ৬। অর্থাৎ ৪ এর গ্রে কোড ৬।

এভাবে করে প্রত্যেকটা সংখ্যার জন্য গ্রে কোড জেনারেট করে এই প্রব্লেমটা সল্ভ করা যাবে।


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    /// kth বিট কে ১ করে দেয় এই ফাংশন
    int setBit(int mask, int k) { return ( mask | (1<<k) ); } 
    /// kth বিট ১ কিনা চেক করে এই ফাংশন
    int checkbit(int mask, int k){ return ((mask>>k) & 1 );  }
    /// kth বিট কে ০ করে দেয় এই ফাংশন
    int resetBit(int mask, int k){ return (mask = (checkbit(mask, k) == 1) ? (mask ^(1<<k)) : mask ); }
    
    
    int BinaryToGray(int n)
    {
        int gray = 0;
        for(int i = 30; i >= 0; i--) ///ইন্টিজার এ টোটাল বিট ৩২টা হয় 
        {
            if(( checkbit(n,i) ^ checkbit(n,i+1) )) /// XOR ১ কিনা চেক করছি। ১ হলে গ্রে কোড এর ith বিট ১ করে দিবো
            {
                gray = setBit(gray, i);
            }
            else gray = resetBit(gray, i); /// না হয় গ্রে কোড এর ith বিট ০ করে দিবো
        }
        return gray;
    }
    vector<int> grayCode(int n) {
        n = pow(2,n);
        vector<int> ans(n);
        for(int i = 0; i<n;i++)
        {
            ans[i] = BinaryToGray(i);
        }
        return ans;
    }
};

Comments

Post a Comment

Popular posts from this blog

URI 2994 Solution

-
URI 2994 - How much earn a Doctor?  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SELECT d . name , ROUND (t . salary, 1 ) FROM doctors as d INNER JOIN ( SELECT id_doctor, SUM( (hours * 150 ) + ((hours* 150.0 * w . bonus) / 100.0 ) ) AS salary FROM work_shifts AS w INNER JOIN attendances AS a ON w . id = a . id_work_shift GROUP BY id_doctor ) AS t ON t . id_doctor = d . id ORDER BY t . salary desc ;
Read more

URI 2996 Solution

-
 URI 2996 - Package Delivery 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 SELECT year , sender, receiver FROM packages AS p INNER JOIN ( SELECT id_package, name AS sender FROM packages INNER JOIN users ON id_user_sender = id WHERE address <> 'Taiwan' ) AS sub1 ON sub1 . id_package = p . id_package INNER JOIN ( SELECT id_package, name AS receiver from packages INNER JOIN users ON id_user_receiver = id WHERE address <> 'Taiwan' ) AS sub2 ON sub2 . id_package = p . id_package WHERE color = 'blue' OR year = 2015 ORDER BY year DESC , sender DESC ;
Read more