বিটের পার্থক্যের সমষ্টি – প্রোগ্রামিং ইন্টারভিউ সমস্যা ৯

সমস্যাঃ একটা অ্যারেতে কতগুলো অঋণাত্মক সংখ্যা আছে। ওই সংখ্যাগুলোর মাঝে যতগুলো জোড়া (pair) আছে, তাদের মধ্যে বিটের পার্থক্যের যোগফল বের করতে হবে। অর্থাৎ, কোনো একটি অ্যারেতে তিনটি সংখ্যা n1, n2, n3 থাকলে বের করতে হবে : n1 ও n2-এর মধ্যে বিটের পার্থক্য + n1 ও n3-এর মধ্যে বিটের পার্থক্য + n2 ও n3-এর মধ্যে বিটের পার্থক্য + n2 ও n1-এর মধ্যে বিটের পার্থক্য + n3 ও n1-এর মধ্যে বিটের পার্থক্য + n3 ও n2-এর মধ্যে বিটের পার্থক্য।

n1 ও n2-এর বিটের পার্থক্য হচ্ছে, সংখ্যা দুটিকে বাইনারিতে প্রকাশ করলে, যতগুলো পজিশনে তাদের বিটগুলো ভিন্ন হয়। যেমন, 7-কে বাইনারিতে প্রকাশ করলে আমরা পাই 111। আর 2-কে বাইনারিতে প্রকাশ করলে পাই 010। তাহলে 7 ও 2-এর মধ্যে প্রথম ও তৃতীয় বিট আলাদা, অর্থাৎ তাদের বিটের পার্থক্য 2।

উদাহরণঃ একটি অ্যারেতে যদি থাকে – [2, 4, 6], তাহলে তাদের সব জোড়ার বিটের পার্থক্য হবে –

f(2, 4) + f(2, 6) + 
f(4, 2) + f(4, 6) +
f(6, 2) + f(6, 4)  = 

2 + 1
2 + 1
1 + 1  = 8

সমস্যাটির সমাধান করতে হলে বিট অপারেশন সম্পর্কে পরিষ্কার ধারণা থাকতে হবে। সমস্যাটি এখানে সমাধান করে যাচাই করা যাবে – https://www.interviewbit.com/problems/sum-of-pairwise-hamming-distance/

সমাধানঃ আমরা একটি নেস্টেড লুপ ব্যবহার করে প্রতি জোড়ার মধ্যে বিটের পার্থক্য বের করতে পারি। তারপর সেগুলো যোগ করে দিতে পারি। বিটের পার্থক্য বের করার কাজটা একাধিকভাবে করা যায়, সহজ কাজ – আমি কোড লিখে দেখালাম না। এই সমাধানের কমপ্লেক্সিটি হবে O(n^2). ইন্টারভিউতে প্রশ্ন দেখেই কোড লেখা শুরু করা যাবে না। ইন্টারভিউয়ারকে বলতে হবে তুমি কোন পদ্ধতিতে সমাধান করতে চাইছ। তারপরে ইন্টারভিউয়ার যদি বলেন কোড লিখতে, তাহলে কোড লেখা শুরু করবে। নেস্টেড লুপ চালিয়ে কোড লিখলে ইন্টারভিউয়ার বলবেন এটার কমপ্লেক্সিটি বের করতে, এবং তারপর বলবেন এটাকে আরো ইফিশিয়েন্ট করতে।

সমস্যাটি O(n) কমপ্লেক্সিটিতেও সমাধান করা যায়। সেক্ষেত্রে আমাদেরকে জানতে হবে একটি সংখ্যা সর্বোচ্চ কত বিটের হবে। ইন্টারভিউয়ারকে সেটি প্রশ্ন করে জেনে নিতে হবে। ধরা যাক, সংখ্যাগুলো 32 বিটের। তখন বিটের প্রতিটি অবস্থানের জন্য (অর্থাৎ ১ম বিট, ২য় বিট, ৩য় বিট … ) কতগুলো সংখ্যায় ওই বিটে 1 আছে (একে বলা হয় সেট বিট) সেটি বের করতে হবে। ধরা যাক, এর মান হচ্ছে count। আর অ্যারেতে মোট সংখ্যা হচ্ছে nটি। তাহলে n – count সংখ্যায় ওই অবস্থানের বিটটি হচ্ছে 0। তাহলে ওই অবস্থানের জন্য বিটের মোট পার্থক্য হবে count * (n – count) * 2। দুই দিয়ে গুণ করার কারণ হচ্ছে, n1, n2 ও n2, n1 আলাদা জোড়া।

হিন্টসঃ একটি সংখ্যা n-এর i-তম (ডান দিক থেকে) বিট 1 কী না, সেটি বেরা যায় n & (1 << i) -এর মাধ্যমে।

 

Facebook Comments

Leave a Reply