এই পর্বটি পড়ার আগে এই দু’টো পর্ব দেখে আসলে উপকৃত হবেঃ

১) বিটওয়াইজ-১

২) বিটওয়াইজ-২

বিটওয়াইজ অপারেটর দিয়ে কত শত কাজ যে করা যায়,তার হিসেব নাই। আজ একটা ”সহজ কিন্তু জটিল” ধরণের সমস্যা নিয়ে একটু আলাপ আলোচনা করবো। অনেকদিন পর লিখতে বসা।

সমস্যাটা অনেকটা এরকম। ধরো,তোমার কাছে ইন্টেজার নাম্বারের একটা ARRAY আছে,যাতে উপাদান সংখ্যা হচ্ছে বিজোড় সংখ্যক। এই ARRAY তে সবগুলা উপাদানই জোড়ায় জোড়ায় আছে,শুধুমাত্র একটা উপাদান আছে যে কিনা একবার মাত্র অবস্থান করতেছে ARRAY টাতে। তোমাকে সেই উপাদানটা খুঁজে বের করতে হবে। একটা উদাহরণ দিই বর্ণনা যেহেতু বললামঃ

                                                                 ARRAY[5] = { 4 , 5 , 3 , 5 , 4 }

তাহলে,আমাদের প্রিন্ট করতে হবে 3 । উল্লেখ্য, জোড়ায় জোড়ায় সংখ্যাগুলো ARRAY টার যেকোনো জায়গাতেই থাকতে পারে। পাশাপাশি থাকতে হবে এমন কোনো কথা নেই।

Okay,এটার সমাধান তো খুবই সহজ! একটা লুপ চালিয়ে চেক করবো নাম্বারগুলার ফ্রিকুয়েন্সি। যার ফ্রিকুয়েন্সি 1 , তাকেই প্রিন্ট করে দিবো! 😀

কিন্তু আমি যদি বলিঃ ” না,এভাবে না। তোমাকে O(n) টাইম কমপ্লেক্সিটিতে এটা করতে হবে।” তখন? ( মানে লুপটা ঘুরবে শুধুমাত্র একবার,ARRAY টার শুরু থেকে শেষ পর্যন্ত ঘুরে এসেই সাথে সাথে রেজাল্ট বলে দিবে,আবার চেক করবে না )

আরো শর্ত দিয়ে দিই,এই যে ARRAYটা নিয়ে তোমরা কাজ করবে,তাতে উপাদান সংখ্যা থাকতে পারে ২^৩১ সংখ্যক! তার মানে,তুমি একটা ARRAY নিয়েও কাজ করতে পারবেনা! কারণ গ্লোবালি ডিক্লেয়ার করলেও একটা Integer Type Array এর হাইয়েস্ট ক্যাপাসিটি হতে পারে 999999999 ( মানে , 10^9 এর কম ) ।

একটু কমপ্লিকেটেড হয়ে গেলো তাইনা? তবে বিটওয়াইজ অপারেটরের XOR অপারেশন জানলে ব্যাপারটি খুবই সহজে সল্ভ করে ফেলা যায়।

XOR যা করে তা হচ্ছে,দুইটি নাম্বারের বাইনারী রিপ্রেজেন্টেশনের বিটগুলো ধরে ধরে কাজ করে। 0 আর 1 পেলে সে আউটপুট দেয় 1 , 1 আর 1 পেলে সে আউটপুট দিবে 0,আর দুইটাই 0 হলে সে আউটপুট ও দিবে 0 . দু’টি একই নাম্বারের উপর XOR এপ্লাই করে দেখি তো কি হয়!

একটু কি বুঝা যাচ্ছে,আমি কি করতে যাচ্ছি? 😀 XOR অপারেশন দু’টো একই নাম্বারের উপর চালালে,আউটপুট হয় জিরো। আর যদি জিরোর সাথে কোনো নাম্বারের XOR করা হয়,তাহলে আউটপুট হয় সেই অশূন্য নাম্বারটাই! আমরা যখন আমাদের GIVEN ARRAY(JUST A SEQUENCE OF NUMBER) টার প্রত্যেক জোড়া জোড়া নাম্বারে XOR চালাতে থাকবো,প্রতিক্ষেত্রে আউটপুট পাবো শুণ্য,আর এই শুণ্যের সাথে অবশেষে সেই একা একা বসে থাকা নাম্বারটির XOR করলে আমরা আউটপুট হিসেবে সেই নাম্বারটিকেই পেয়ে যাবো! 😀

আমি জানি তোমাদের মনে একটা প্রশ্ন জেগেছে,আমি নিচে সেটার উত্তর ও দিয়ে দিচ্ছিঃ

প্রশ্নটা এরকম জাগতে পারতোঃ ”আচ্ছা ভাইয়া,যদি ARRAY তে একই উপাদানগুলো পাশাপাশি না থেকে ছড়িয়ে ছিটিয়ে থাকতো,তবেও কি দু’টো দু’টো নাম্বার ধরে XOR করে দিলে আমি সঠিক আউটপুট পেতাম?”

উত্তরঃ হ্যাঁ পেতে। XOR এক ধরণের Encrypt Operator হিসেবেও কাজ করে! একবার একটা নাম্বারকে সে পেলে XOR করার পরেও তার প্যাটার্নে সেটি সেভড থাকে। পরবর্তীতে সে নাম্বারটি আবার পেলে,সাথে সাথে সেই প্যাটার্নটি নষ্ট হয়ে যায়। 🙂

অসাধারণ একটি জিনিস শিখে ফেললে! হ্যাপি কোডিং! আর আমি কোডটা কেমন দেখতে তাও দিয়ে দিচ্ছিঃ

• Bio
• Facebook
• Latest Posts

Sadman Sakib

I am nobody.

Sadman Sakib

Latest posts by Sadman Sakib (see all)

• আংশিক ভগ্নাংশে প্রকাশ - August 29, 2017
• পর্যায়ক্রমিক Permutation! - May 11, 2017
• LightOJ 1137 – Expanding Rods – গভীরে গিয়ে আলোচনা - April 8, 2017