অনলাইন জাজ সিরিজ – ১০ (UVa 10931 – Parity)

UVa Online Judge এ আমার সলভ করা প্রথম প্রবলেমটা নিয়ে আজকে আলোচনা করব। 🙂

UVa 10931 – Parity

উপরের লিংক থেকে প্রবলেমটা পড়ে ফেল। তেমন কোন অস্পষ্টতা বা confused করার মত বাড়তি কথাবার্তা নেই। এক কথায় বলতে হলে এখানে বের করতে বলেছে কোন একটা int নাম্বারের binary representation এবং তাতে কতটি 1 আছে সেই সংখ্যাটি। ইনপুট দেয়া হবে একটি করে পূর্ণ সংখ্যা I, যেখানে 1 ≤ I ≤ 2147483647. অর্থাৎ I ভেরিয়েবলটি int type এর নিলেই হবে। long বা long long type এর দরকার হবে না। ইনপুট হিসেবে 0 (zero) পেলে প্রোগ্রামটি terminated হবে। এক্ষেত্রে একটি লুপের ভিতরে ইনপুট নিয়ে প্রসেসিং করে আউটপুট দেখানোর কাজটা চলতে থাকবে আর প্রতিবার ইনপুট নিয়েই চেক করতে হবে তা শূণ্য কিনা। শূণ্য হলে লুপটা break করে দিতে হবে।

Test care, EOF ও ইনপুট নেয়ার বিভিন্ন উপায় জানা যাবে এখান থেকে।

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

তাহলে আসো এখন স্টেপগুলো একটার পর একটা সাজাই যে কিভাবে এটা সলভ করা যায়। প্রথমে সংখ্যাটা ইনপুট নিব। এরপর এই সংখ্যাকে একটা লুপের মধ্যে প্রতিবার ২ দিয়ে MOD করর এরপর ২ দিয়ে ভাগ করব এই মড আর ভাগ করার কাজ ততক্ষণ চলতে থাকবে যতক্ষণ না পর্যন্ত সংখ্যাটি শূণ্য না হয়ে যায়। কোডটা অনেকটা এরকমঃ

while(num>0)
{
   binary[index++] = num % 2; //index is an int type variable. initialized by 0.
   num = num / 2 ;
}

3 নম্বর লাইনে binary একটা int type array. প্রতিবার num কে ২ দিয়ে মড করে সেই রেজাল্টটা এরেতে রেখে দেয়া হচ্ছে। এরপর সংখ্যাটাকে দুইভাগ করা হচ্ছে। এভাবে একটা সময় সংখ্যাটি শূণ্য হয়ে যাবে। তখন লুপটা ব্রেক করবে এবং binary array-তে উল্টা ভাবে num এর binary representation-টা পাওয়া যাবে। এখন এই binary array কে উল্টা ভাবে প্রিন্ট করলেই num এর বাইনারি সংখ্যা পাওয়া যাবে।

আমাদের প্রথম কাজ করা শেষ। দ্বিতীয় কাজটা হচ্ছে কয়টা 1 আছে এই বাইনারি নাম্বারে সেটা বের করা। যেহেতু তোমার কাছে বাইনারি ডিজিটগুলোর এরে আছে তাই এই এরেতে একটা লুপ ঘুরিয়েই গুণে ফেলতে পার। সেক্ষেত্রে কোডটা হতে পারে এরকমঃ

for(i = 0; i<index; i++)
{
    if(binary[i]==1)
        parity++; //it is an int type variable. initialized by 0

}

এখন আউটপুটের ফরমেট অনুযায়ী এরেটা উল্টা দিক থেকে প্রিন্ট কর আর parity এর value প্রিন্ট কর। তাহলেই কাজ শেষ।

আচ্ছা আসলেই কি কাজ শেষ? নাহ… উপরের কোডটাকে বা সিসটেমটাকে আরেকটু ঘষামাজা করে better performance পাওয়া যেতে পারে। আমরা শুধুমাত্র ১ এর সংখ্যা গুণার জন্য একটা লুপ চালিয়েছি। এটার আসলে কোন দরকারই নাই। যখন binary array তে সংখ্যাগুলো assign করছিলাম তখনই কিন্তু আমরা একটা চেক রাখতে পারতাম যে সংখ্যাটা ১ কিনা। প্রথম কোডে এবার কিছু পরিবর্তন আনিঃ

while(num>0)
{
   rem = num % 2;
   binary[index++] = rem; //index is an int type variable. initialized by 0.
   
   if(rem==1)
      parity++;

   num = num / 2 ;
}

1 ও 2 উভয় কোডের কাজই 3 নাম্বার কোড ব্লকে করা হয়েছে। এতে প্রোগ্রামের efficiency অনেকখানি বাড়লো। কোন ভাবে এই কোডকে কি আরেকটু faster করা যায়?

আমরা জানি Mod operation, multiplication, divide operation অনেক costly. অর্থাৎ এগুলো করতে আমাদের পিসি’র জান বের হবার অবস্থা হয় (আক্ষরিক অর্থে নয়; সময় বেশি লাগা বুঝানো হয়েছে)। কিন্তু সেই তুলনায় bitwise operation অনেক অনেক বেশি দ্রুত কাজ করে। আমরা যদি এই কোডে থাকা মড অপারেশন আর ভাগ অপারেশনগুলোকে বাদ দিয়ে বিটওয়াইজ অপারেশন চালাতে পারি তাহলে কিন্তু প্রোগ্রামটা আরেকটু ইফিসিয়েন্ট হবে। কোডটা হতে পারে এরকমঃ

while (num>0)
{
    if((num & 1)==1){
        parity++;
        binary[index++] = 1;
    }
    else
        binary[index++] = 0;

    num = num >> 1;
}

৩ নাম্বার লাইনে চেক করা হয়েছে num এর বাইনারি সংখ্যার শেষ ডিজিটটা 1 কিনা। এটা কিভাবে কাজ করে তার বিস্তারিত জানতে পারবে জোড় বিজোড় বের করার ৫ টি পদ্ধতি এই পোস্টটি থেকে। যদি শেষ ডিজিটটি ১ হয় তাহলে parity এর মান ১ বাড়ানো হচ্ছে এবং বাইরানি এরেতে ১ রাখা হচ্ছে। অন্যথায় বাইনারি এরেতে শূণ্য রাখা হচ্ছে কেননা দুটি সংখ্যার মধ্যে AND operation হলে ফলাফল 1 অথবা 0-ই হবে।  আর ১০ নাম্বার লাইনে num-কে 1 bit right shift করা হয়েছে। আর ইতমধ্যেই জোড় বিজোড় বের করার পোস্টের মাধ্যমে তুমি জেনে গেছ যে কোন সংখ্যাকে 1 bit right shift করা হলে সংখ্যাটি দুই ভাগ হয়ে যায় বা এটি ২ দিয়ে ভাগ করার মতই কাজ করে। কিন্তু ২ দিয়ে ভাগ করার চেয়ে ১ বিট রাইট শিফট করলে এতে কম সময় দরকার হয়।

আমাদের উচিত কোন একটা প্রবলেম সলভ করার পর একটু চিন্তা করা যে প্রবলেমটা আরো efficiently সলভ করার কোন উপায় আছে কিনা। হয়ত এতে UVa তে সলভ করা প্রবলেমের সংখ্যা কম হবে। আমরা কি আসলে সংখ্যা বাড়ানোর জন্য সলভ করি? 🙂