<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Masud Parves on Medium]]></title>
        <description><![CDATA[Stories by Masud Parves on Medium]]></description>
        <link>https://medium.com/@masudparves?source=rss-81b552cf3066------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*5QkF8HZ3ZXMV0NKtTz19_Q.jpeg</url>
            <title>Stories by Masud Parves on Medium</title>
            <link>https://medium.com/@masudparves?source=rss-81b552cf3066------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Tue, 17 Nov 2026 19:57:44 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@masudparves/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Interview Preparation ( Problem Solver to Software Engineer )]]></title>
            <link>https://medium.com/@masudparves/interview-preparation-problem-solver-to-software-engineer-ec1eb07a6b56?source=rss-81b552cf3066------2</link>
            <guid isPermaLink="false">https://medium.com/p/ec1eb07a6b56</guid>
            <category><![CDATA[interview-bangla]]></category>
            <category><![CDATA[interview-preparation]]></category>
            <category><![CDATA[problem-solving]]></category>
            <category><![CDATA[coding-test]]></category>
            <category><![CDATA[interview-topics]]></category>
            <dc:creator><![CDATA[Masud Parves]]></dc:creator>
            <pubDate>Sat, 11 Jul 2020 07:12:19 GMT</pubDate>
            <atom:updated>2020-07-11T07:13:49.928Z</atom:updated>
            <content:encoded><![CDATA[<h3>Interview Preparation [Problem Solver to Software Engineer ]</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4Q9e6b7IfrZdyV_Enwd3VQ.jpeg" /></figure><p>বিসমিল্লাহির রহমানির রাহিম,</p><p>প্রায় সময় অনেকেই একটা প্রশ্ন করে কিভাবে Coding Test বা Interview এর জন্য প্রিপারেশন নেওয়া যেতে পারে । আগেই বলে নেওয়া ভালো যে বিভিন্ন কোম্পানির Recruitment Process আলাদা আলাদা হয়ে থাকে । Recruitment Process নিয়ে আমাদের আগের একটা নোট লিখা আছে চাইলে সেটা একবার দেখে আসতে পারেন। [link : <a href="http://shorturl.at/huEW4?fbclid=IwAR2C8_5sNN9B7KaJuiC_c1KnQ3LRQbECSToqMbuba1mrkGpftdWe9PVgYjQ">shorturl.at/huEW4</a>]</p><blockquote>এই নোটে আমি শুধুমাত্র আমাদের দেশের বিভিন্ন কোম্পানির Coding Test এবং Interview ধাপে পাশ করতে কেমন প্রিপারেশন নেওয়া যায় বা কি কি টপিক্স কভার করা যেতে পারে তা নিয়ে লিখবো ।</blockquote><p>যেহেতু আমার অভিজ্ঞতা খুবই অল্প তাই ভুল-ভ্রান্তি হলে ক্ষমা করবেন :)</p><p>Coding Test : আমাদের দেশের যে যে কোম্পানি গুলো কোডিং টেষ্টের মাধ্যমে Recruitment করে থাকে তাদের প্রায় সবাই কাছাকাছি লেভেলের প্রবলেম সল্ভ করতে দিয়ে থাকে । আপনি যদি ভার্সিটিতে Problem Solving বা ACM করে থাকেন তাহলে আপনার জন্য এই ধাপটি অতিক্রম করতে খুব বেশী বেগ পেতে হবে না। তাই বলে এমন নয় যে আপনি Problem Solver না হলে এই ধাপটি অতিক্রম করতে পারবেন না বা খুবই কষ্টসাধ্য হবে । আমার পরিচিত অনেকেই আছেন যারা কিনা ACM করেনি কিংবা Problem Solver ছিলেন না ।</p><p>যেভাবে প্রিপারেশন নেওয়া যেতে পারেঃ কিছু কোম্পানি আছে যেখানে আপনাকে কোনো ধরনের Library Function ইউজ করতে দিবে না । আবার এমন কিছু কোম্পানি আছে যেখানে আপনাকে Library Function ইউজ করতে দিবে । তাই আমি প্রিপারেশন নেওয়ার সময় Library Function ব্যাবহার না করেই প্রিপারেশন নিতে বলবো ।</p><p>প্রিপারশন সময়কালে আপনি বিভিন্ন অনলাইন জাজে প্রবলেম সল্ভ করতে পারেন । সেক্ষেত্রে leetcode.com এবং interviewbit.com বেশ ভালো চয়েজ বলে আমি মনে করি। এখানে দেশী-বিদেশী বিভিন্ন কোম্পানিতে আসা প্রবলেমও থাকে । এবং একটা ধারনাও হয়ে যায় প্রবলেম কেমন আসতে পারে সেইটার।<br>Cracking The Coding Interview বইটা পড়া উচিৎ এখানে সাবলীল ভাষায় Coding Interview নিয়ে লেখা হয়েছে । বইটির পিডিএফ ভার্ষন গুল করলেই পেয়ে যাবেন।</p><p>টপিকঃ যেহেতু আমি আগেই বলেছি Library Function ব্যাবহার না করাই ভালো , আমরা এমন কিছু টপিক চয়েজ করতে পারি যা Coding Test কালে Library Function ব্যাবহার ছাড়া Implement করতে বেগ পেতে না হয় । যেমনঃ</p><ul><li>Arrays and Strings</li><li>Linked List, Stack, Queue, Heap</li><li>Permutation, Combination, Sub Set</li><li>Recursion, Backtracking, Basic DP [ basic memorization ]</li><li>Basic Graph Theory [BFS, DFS, Topological Sort, etc ]</li><li>Basic Sorting ( n² )</li><li>Basic Searching [ Linear Search, Binary Search ]</li></ul><p>উপরের টপিক গুলার উপরে প্রাকটিস করা যেতে পারে। সাথে এই টপিক গুলার জন্য Cracking The Coding Interview এর নির্দিষ্ট সেসন গুলো দেখে নেয়া যেতে পারে ।</p><p>Interview Preparation : Interview সাধারণত দুইটা পার্টে হয়ে থাকে Technical Part, Non-technical Part . Technical Part টি সাধারণত প্রোজেক্ট লিডরা বা টিমলিড রা নিয়ে থাকেন । যেখানে বিভিন্ন Technical Part নিয়ে প্রশ্ন করে থাকেন । আর Non-Technical Part সাধারণত কোম্পানির HR নিয়ে থাকেন । কখনো কখনো দুইটা পার্ট একই সাথে হয়ে থাকে । আবার কখনো কখনো আলাদা ভাবে হতে পারে । এখানে আমি টেকনিকাল পার্ট নিয়ে কিছুটা আইডিয়া দিবো ।</p><p>Technical Interview : এই ধাপটি অতিক্রম করতে কিছু টপিকের উপর সুস্পষ্ট ধারণা থাকা লাগবে । যেমনঃ</p><ul><li>Object Oriented Programming</li><li>Operating System, Computer Networking</li><li>Database Management System</li><li>Clear Concept about Time &amp; Memory Complexity</li><li>Basic কিছু Data Structure &amp; Algorithm এর ক্লিয়ার কন্সেপ্ট। যেমনঃ (Trie, Max-Heap, Min-Heap, Stack , Queue, Hash , etc) [ তবে এখানে কোনো প্রবলেম সল্ভ করতে দিবেনা , বেসিক প্রশ্ন করবেন PL রা ]</li><li>Basic Version Control [Git]</li><li>সাধারণত Object Oriented Design , System Design ফ্রেশার্সদের জন্য এপ্লিকেবল নয় । তবে বেসিক ধারণা থাকলে এডভানটেজ পাওয়া যাবে ।</li></ul><p>Technical Interview এর জন্য আমি <a href="https://l.facebook.com/l.php?u=http%3A%2F%2Fwww.geeksforgeeks.org%2F%3Ffbclid%3DIwAR0cdzND-K0V_iE0rFEMue3tiIBT-MLdXJbUjlf4-uS5X5SZ-WXSPfGtPxY&amp;h=AT3eTxuc47LZ5CGTdq216bTpquYuhuOjtTxfUz6tuJNvMfP_AjuM0lk5Pur2ArTHn31L8qIdh1YFPfH43cmouIsJxCUuifEqusNodIJ_VlGkHtaX7b3m-LzzSfcYcWpAWlAG_A">www.geeksforgeeks.org</a> এবং <a href="https://l.facebook.com/l.php?u=http%3A%2F%2Fwww.zentut.com%2F%3Ffbclid%3DIwAR1g7Gfky8kzgKnZOG4xvL3WQYx3j-e6q0FMXSzsr7QFmBF3SjcMpPW7nn4&amp;h=AT1wTHZXudFbelLY6tVtre_B9CsSXj8Axye1-Pc4hGOpDAwCi1cF_-yb76Y_L9GKIIG5kwaRrE-WA5RohLUBbMlPM4h4U2d1cRi6FemKDnWLZ3FJ4d51kNhQ5A2JSpQoXt4B5w">www.zentut.com</a> সাইটি সাজেশন করতে পারি ।</p><p>Technical Part এর একটা গুরুত্বপূর্ণ পার্ট হচ্ছে আপনার সিভি এবং সিভিতে থাকা ইনফরমেশন। এখানে আপনার সিভি থেকে বেশ কিছু প্রশ্ন থাকতে পারে । যেমনঃ আপনার ভার্সিটির প্রজেক্ট কিংবা থিসিস নিয়ে প্রশ্ন থাকতে পারে । আপনার যদি কিছু ছোট্ট খাটো এপ করা থাকে সেখান থেকে প্রশ্ন থাকতে পারে । তাই নিজের সিভি নিয়ে একটু নিজেই পড়াশোনা করে আসা উচিৎ ।</p><blockquote>কোনো কোম্পানিতে Coding Test কিংবা Interview দেওয়ার আগে <a href="https://l.facebook.com/l.php?u=https%3A%2F%2Fwww.glassdoor.com%2F%3Ffbclid%3DIwAR3hjJo5J6dcbxSATYEMyYKr_4IvXq7MUDA9Bop4U62E6X64Yt4RB3WwJQI&amp;h=AT1kYFuRH3dD6vBZNLJFOaxcO1uc1yD21tPop2xlj6P2cZI9deZjH36HY2I85_oX96CYqapbmwUa0hl6TEFJruzDOZefcB6kCw13GmzpM6fwljB0g82WB2mIT4Nc6jkvwSXOVw">https://www.glassdoor.com</a> থেকে সেই কোম্পানির সম্পর্কে কিছুটা ধারণা নিয়ে আসা উচিৎ।</blockquote><p>আপাতত আর কিছু মাথায় আসছেনা , যদি আসে পরে যুক্ত করে দিবো ।</p><p>আপনাদের মতামত একান্তই কাম্য ।</p><p>হ্যাপি কোডিং 🙂</p><p><strong>Masud Parves </strong><br>Software Engineer</p><p>Samsung R&amp;D Institute Bangladesh.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ec1eb07a6b56" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Z Algorithm [String Matching Algorithm পর্ব-০১]]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/z-algorithm-string-matching-algorithm%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A6%E0%A7%A7-663527f83131?source=rss-81b552cf3066------2</link>
            <guid isPermaLink="false">https://medium.com/p/663527f83131</guid>
            <category><![CDATA[algorithm-bangla]]></category>
            <category><![CDATA[algoz]]></category>
            <category><![CDATA[string-matching]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[z-algorithm]]></category>
            <dc:creator><![CDATA[Masud Parves]]></dc:creator>
            <pubDate>Tue, 14 Jan 2020 12:31:50 GMT</pubDate>
            <atom:updated>2020-01-15T02:05:17.572Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*9xv8X9df2wojULtL4Gx9sg.jpeg" /></figure><p>আজ আমরা <strong>Z-Algorithm</strong> নিয়ে আলোচনা করবো। <strong>Z Algorithm</strong> এর মাধ্যমে আমরা কোনো স্ট্রিং থেকে লিনিয়ার টাইমে প্যাটার্ন সার্চ করতে পারি। যেমনটা <strong>KMP</strong> এলগরিদমে করা হয়। <strong>KMP</strong> এবং <strong>Z Algorithm</strong> এর কমপ্লেক্সিটি একই কিন্তু <strong>Z Algorithm</strong> তুলনামূলক অনেকটা সহজ।</p><p><strong>Z Algorithm </strong>এ আমাদের মূল কাজ হচ্ছে একটা <strong>Array</strong> ক্যালকুলেট করা। যেই অ্যারেটাকে আমরা <strong>Z Array</strong> বলে থাকি।</p><h4><strong>Z Array</strong></h4><p><strong>Z Array</strong> তে প্রতিটা পজিশনে জন্য আমরা ওই পজিশন থেকে ডানদিকে কতটুকু স্ট্রিং মূল স্ট্রিং এর প্রিফিক্স <strong>(Longest Prefix)</strong> হিসেবে আছে তা রাখবো।</p><blockquote>আরও একটু সহজ করে বলতে গেলে,<strong> Z Array</strong> তে প্রতিটা পজিশন (i≥0 থেকে <strong>length of string</strong>) এর জন্য, ওই পজিশন থেকে ডান দিকে প্রথম থেকে কয়টা ক্যারেক্টার ম্যাচ করে এই তথ্য সংরক্ষণ করবো। <strong>Z Array</strong> এর প্রতিটা পজিশনের এই ভ্যালুকে আমরা <strong>Z value</strong> বলি।</blockquote><p>উদাহরণঃ</p><p>ধরি string <strong>s</strong>=”<strong>aabcaabxaaaz</strong>”;</p><pre><strong>Example:</strong><br>Index            0   1   2   3   4   5   6   7   8   9  10  11 <br>String           a   a   b   c   a   a   b   x   a   a   a   z</pre><p>এই উদাহরণের জন্য Z Array ক্যালকুলেট করা যাকঃ</p><p>Z[0] এর জন্য স্বভাবতই সম্পূর্ণ স্ট্রিংটি প্রিফিক্স হিসেবে ম্যাচ করে।</p><p>তাই Z[0] = 12 হয়।</p><p>তবে Z Array হিসাব করার সময় প্রবলেমের উপর ভিত্তি করে,</p><p>Z[0] = 0 অথবা Z[0] = n; ধরা হয়। [<strong>N.B. n = স্ট্রিং এর লেংন্থ বোঝানো হয়েছে</strong>]</p><p><em>তাহলে</em>,</p><p>Z[0] = 0 | n , এখানে n মানে স্ট্রিং এর লেন্থ বোঝানো হয়েছে।</p><p>Z[1] = 1, কেননা পজিশন 1 এর জন্য প্রথম থেকে শুধু একটি ক্যারেক্টার ম্যাচ করে । তা হচ্ছেঃ a</p><p>Z[2] = 0, কেনোনা পজিশন 2 এর জন্য প্রথম থেকে একটিও ক্যারেক্টার ম্যাচ হয়নি।</p><p>Z[3] = 0, কেনোনা পজিশন 2 এর জন্য প্রথম থেকে একটিও ক্যারেক্টার ম্যাচ হয়নি।</p><p>Z[4] = 3, কেননা পজিশন 4এর জন্য প্রথম থেকে তিনটি ক্যারেক্টার ম্যাচ করে । তা হচ্ছেঃ aab</p><p>z[5] = 1, কেননা পজিশন 5 এর জন্য প্রথম থেকে শুধু একটি ক্যারেক্টার ম্যাচ করে । তা হচ্ছেঃ a</p><p>Z[6] = 0 , কেনোনা পজিশন 6 এর জন্য প্রথম থেকে একটিও ক্যারেক্টার ম্যাচ হয়নি।</p><p>Z[7] = 0, কেনোনা পজিশন 7 এর জন্য প্রথম থেকে একটিও ক্যারেক্টার ম্যাচ হয়নি।</p><p>Z[8] = 2, কেননা পজিশন 8 এর জন্য প্রথম থেকে তিনটি ক্যারেক্টার ম্যাচ করে। তা হচ্ছেঃ aa</p><p>Z[9] = 2, কেননা পজিশন 9এর জন্য প্রথম থেকে তিনটি ক্যারেক্টার ম্যাচ করে। তা হচ্ছেঃ aa</p><p>Z[10] = 1, কেননা পজিশন 10এর জন্য প্রথম থেকে একটি ক্যারেক্টার ম্যাচ করে। তা হচ্ছেঃ a</p><p>Z[11] = 0, কেনোনা পজিশন 11এর জন্য প্রথম থেকে একটিও ক্যারেক্টার ম্যাচ হয়নি।</p><p>তাহলে উপরের স্ট্রিং এর জন্য আমাদের <strong>Z Array</strong> ক্যালকুলেশন এমনঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/605/1*kmdROPfX2FWcFEzCWriHUg.png" /></figure><h4>কিভাবে <strong>Z Array</strong> ক্যালকুলেট করা যায়?</h4><blockquote>Brute Force or Trivial algorithm :</blockquote><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/1fc9ef14c2df3528fa73cb1ecba98c6e/href">https://medium.com/media/1fc9ef14c2df3528fa73cb1ecba98c6e/href</a></iframe><p>এই কোডের Time Complexity O(n²). যা অবশ্যই ভালো নয় । আমারা এটাকে কমিয়ে O(n) এ নিয়ে আসতে পারি। :)</p><p>এখানে আমাদের কিছু Observations এর মাধ্যমে Z Array টা O(n) এ ক্যালকুলেট করতে পারি।</p><p>একটা নতুন উদাহরণ দেখিঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/895/1*oJG8n7_uilqyjRfo_UCALQ.png" /></figure><p>এখান আমরা প্রতিটা পজিশন i জন্য Z value হিসাব করার সময় চেষ্টা করবো পূর্বে হিসাব করা মান ব্যবহার করতে। এতে করে আমাদের ক্যালকুলেশন অনেকটাই কমে যাবে।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/895/1*hdln9SPQ2zKEdntWhWEgrQ.png" /></figure><p>এখন ২য় পিকচারে যদি আমরা খেয়াল করি পজিশন 9 এর Z value = 8। এর মানে কী দাঁড়ায়?</p><p>তার মানে, এই পজিশন i=9 থেকে ৮ লেন্থের স্ট্রিং <strong>aabxaabx</strong> প্রথম থেকে হুবহু ম্যাচ করে [লাল এবং সবুজ বক্স এর স্ট্রিং হবহু ম্যাচ করে]।</p><p>যেহেতু এই 8 লেন্থ এর স্ট্রিং প্রথম থেকে হুবহু ম্যাচ করে তাই আমরা এই ম্যাচ করা স্ট্রিংকে বলবো ম্যাচিং সিগমেন্ট। ম্যাচিং সিগমেন্টের শুরু ইনডেক্সকে বলবো L এবং শেষ প্রান্তকে বলবো R. [ছবিতে সবুজ বক্সটি]</p><p>আমরা একটু খেয়াল করলে দেখবো <strong>ম্যাচিং সিগমেন্টের প্রতিটা পজিশনের ক্যারেক্টার প্রথম থেকে i-L তম ক্যারেক্টারের সাথে ম্যাচ করে</strong> এবং <strong>Z[i-L] আমরা আগেই ক্যালকুলেট করে এসেছি</strong>। যা আমরা এই পজিশনের Z value হিসাব করার সময় ব্যাবহার করবো।যদি আমাদের পজিশন i ম্যাচিং সিগমেন্টের ভেতর তাহলে, Z[i] = Z[i-L] ইনিশিয়ালি ভাবতে পারি।</p><p>ভাবতে পারি মানে আমরা এখনো শিউর বলতে পারিনা Z[i] এর Z[i-L] এর সমান হবে কিনা । Z[i] এর ভ্যালু Z[i-L] এর সমান হতে পারে, Z[i] এর ভ্যালু Z[i-L] এর থেকে ছোট হতে পারে, Z[i] এর ভ্যালু Z[i-L] এর থেকে বড় হতে পারে। কিভাবে?</p><p>ধরি, আমরা ম্যাচিং সিগমেন্টের এর i তম পজিশনে আছি এবং এই i থেকে R এর ভিতর কেবল ৪টা ক্যারেক্টার বাকি আছে। কিন্তু Z[i-L] এর ভ্যালু প্রিভিয়াসলি ক্যালকুলেট করে আসছি 6 তাহলে কি আমরা Z[i] = 6 বসাতে পারি? পারিনা, কারণ আমাদের সামনে এতোগুলা ক্যারেক্টার আসলে নেই। তাহলে ম্যাচ করার প্রশ্ন আসেনা। একটা উদাহরণ দেখে ক্লিয়ার হওয়া যাক।</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/633/1*QJIFygpnmUO2eFjvP1OQoQ.png" /></figure><p>এই উদাহরণে, আমাদের ম্যাচিং সিগমেন্ট L=7 থেকে R=11 পর্যন্ত। তাহলে পজিশন i=10 ক্যারেক্টার আমাদের ম্যাচিং সিগমেন্টের অন্তর্ভুক্ত। তাই আমাদের s[i] এবং s[L-i]ক্যারেক্টার সমান। কিন্তু আমরা ছবিতে দেখতে পাচ্ছি Z[i] এর মান Z[i-L] এর থেকে কম হয়েছে। কারণ i থেকে R এর ভিতর কেবল মাত্র R-i+1 = 11–10+1 = 2 টা ক্যারেক্টার আছে, যেখানে Z[i-L] = 3।</p><p>কিন্তু যদি i থেকে R এর ভিতরে যদি ৩টা ক্যারেক্টার থাকতো তাহলে মান Z[i] = Z[i-L] হতো। তাই আমরা বলতে পারি, ম্যাচিং সিগমেন্টের ভিতরে <strong>Z[i] = min(R-i+1, Z[i-L])</strong> হতে পারে।</p><p>এখন দেখি কখন Z[i] এর ভ্যালু Z[i-L] থেক বড় হতে পারেঃ</p><p>উদাহরণঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/895/1*eX84e-rMCm8OiVTGa_vpGA.png" /></figure><p>উদাহরণে, পজিশন i=13 আমাদের ম্যাচিং সিগমেন্টে পড়ছে । যা s[i] এবং s[i-L] ক্যারেক্টারের সমান।</p><p>আমাদের Z[i]=Z[i-L] এর সমান হওযার কথা ছিলো কিন্তু এখানে সিগমেন্টের বাহিরের এলিমেন্টের সাথেও ম্যাচ করে বলে Z[i] এর মান Z[i-L] এর তুলনায় বৃদ্ধি পেয়েছে।</p><p>তারমানে যদি সিগমেন্টের পরেও ম্যাচ করে তাহলে Z[i] এর মান বাড়াবো। তাহলে উপরের ছবিতে কিভাবে পজিশন i=13 এর জন্য আমরা Z[i] হিসাব করবো? সিগমেন্টের বাহিরে ম্যাচ আছে কিনা তা যাচাই করার জন্য কোন পজিশন এর সাথে কোন পজিশন কম্পেয়ার করবো? আসুন দেখি,</p><p>ছবিতে পজিশন i = 13 এর যায়গাতে ইনিশিয়ালি</p><p>Z[i] = Z[i-L]</p><p>বা, Z[i] = 4 বসাবো।</p><p>তারপর সামনে সিগমেন্টের বাহিরে ম্যাচ আছে কিনা সেটা চেক করার জন্য s[i+z[i]] এবং s[z[i]] ক্যারেক্টারের সাথে কম্পেয়ার করবো যদি ম্যাচ হয় তাহলে Z[i] এর মান বাড়াবো। কিন্তু কেনো?</p><p>কারণটা খাতা কলম নিয়ে দাগাদাগি করার জন্য ব্যাখ্যা করলাম না। আরেকটা কথা মনে করিয়ে দেই, যখনই একটা নতুন সিগমেন্ট পাবো তার <strong>L</strong> এবং<strong> R</strong> আপডেট করতে যেনো আমরা না ভুলি 😊</p><p>এভাবে আমরা ম্যাচিং সিগমেন্টের অন্তর্ভুক্ত পজিশনের ভ্যালুর জন্য পুর্বে হিসাব করা ভ্যালু ব্যাবহার করে পুরো Z Array টা হিসাব করে ফেলতে পারি।</p><blockquote>কোডঃ</blockquote><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/f003be0d2ff87079063cec764ad5bb1f/href">https://medium.com/media/f003be0d2ff87079063cec764ad5bb1f/href</a></iframe><h4>Complexity</h4><p>এখানে প্রতিটা পজিশনের জন্য আলাদা করে লুপ ব্যাবহার করতে হয়নি। শুধু মাত্র সেই পজিশনের জন্য লুপ ব্যাবহার করেছি যেখানে ম্যাচিং সিগমেন্ট পাইনি। তাই ভিতরের লুপটা সব মিলিয়ে O(n) বার চলেছে [<strong>এ ধরনের লুপকে Amortize Loop বলে থাকে</strong>]এবং বাহিরের লুপ O(n) বার চলেছে।</p><p>তাই সম্পূর্ণ কমপ্লেক্সিটি O(n+n) বা O(n) হবে।</p><p>আজ এই এখানেই শেষ করলাম। আগামী পর্বে Z এলগরিদম দিয়ে প্যাটার্ন সার্চ করা যায় কিভাবে তা দেখবো। সাথে কিছু প্রবলেম নিয়ে আলোচনা করার চেষ্টা করবো।</p><p>আল্লাহ হাফেজ।</p><p>হ্যাপি কোডিং 😊</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=663527f83131" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/z-algorithm-string-matching-algorithm%E0%A6%AA%E0%A6%B0%E0%A7%8D%E0%A6%AC-%E0%A7%A6%E0%A7%A7-663527f83131">Z Algorithm [String Matching Algorithm পর্ব-০১]</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Kruskal’s Algorithm [ Minimum Spanning Tree ]]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/kruskals-algorithm-minimum-spanning-tree-74fda4b98638?source=rss-81b552cf3066------2</link>
            <guid isPermaLink="false">https://medium.com/p/74fda4b98638</guid>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[kruskals-algorithm]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[minimum-spanning-tree]]></category>
            <dc:creator><![CDATA[Masud Parves]]></dc:creator>
            <pubDate>Wed, 02 Jan 2019 05:43:15 GMT</pubDate>
            <atom:updated>2019-01-02T05:43:15.285Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cUOknyEHrQ6wGqynmp__Eg.jpeg" /></figure><p>আজ আমরা মিনিমাম স্প্যানিং ট্রি বের করার এলগরিদম শিখবো । মিনিমাম স্প্যানিং ট্রি বের করার দুইটা এলগরিদম আছে ।<strong> </strong>Kruskal’s এবং Prim’s এলগরিদম । দুইটাই Greedy এলগরিদম । তবে আজ আমরা Kruskal’s এলগরিদম নিয়ে আলোচনা করবো।</p><p><strong>স্প্যানিং ট্রিঃ</strong> স্প্যানিং ট্রি হচ্ছে এমন একটি সাবগ্রাফ যেখানে মূল গ্রাফের সবগুলো নোড বিদ্যমান থাকবে এবং গ্রাফে এজ সংখ্যা হবে নোড সংখ্যা থেকে এক কম। তার মানে মূল গ্রাফের নোড সংখ্যা যদি n হয় তাহলে স্প্যানিং ট্রি এর নোড সংখ্যাও হবে n এবং এজ সংখ্যা হবে n-1 টি।</p><blockquote><strong>কোন গ্রাফের যদি n টি নোড এবং n-1 টি এজ থাকে তাহলে তাকে ট্রি বলে । ট্রিতে কোন সাইকেল থাকে না ।</strong></blockquote><p>এখন একটি গ্রাফের অনেকগুলো স্প্যানিং ট্রি থাকতে পারে তাই যে স্প্যানিং ট্রি এর এজগুলোর কস্ট/ওয়েটের যোগফল মিনিমাম সেই স্প্যানিং ট্রিকে মিনিমাম স্প্যানিং ট্রি বলে।</p><p><strong>Kruskal’s Algorithm : </strong>এখন আমরা Kruskal’s Algorithm এর মাধ্যেমে মিনিমাম স্প্যানিং ট্রি বের করবো। আমি আগেই বলেছি Kruskal’s একটি Greedy এলগরিদম । Greedy মানে হচ্ছে লোভি । আর লোভিরা কি করেন?যেভাবে তার লাভ বেশী হবে সেই উপায় কাজ করেন । আমরাও তাই করবো ।</p><blockquote><strong>আমরা যেহেতু Greedy এলগরিদম করছি , তার মানে আমাদের প্রতিটা স্টেপের চয়েজ ওই সময়ের জন্য বেষ্ট হতে হবে। এবং তারপর সবগুলো স্টেপের পর আমরা আমাদের বেষ্ট উত্তর পাবো । মূলত এটাই গ্রিডির মূলনীত ।</strong></blockquote><p>যেহেতু আমরা একটি গ্রাফ থেকে মিনিমাম স্প্যানিং ট্রি বিল্ড করবো । তারমানে আমরা মিনিমাম কস্টের/ওয়েটের এজগুলো কে নিয়ে একটি ট্রি বিল্ড করবো যেখানে আমরা খেয়াল করবো যাতে ট্রিতে কোন লুপ / সাইকেল তৈরি হয়ে না যায়।</p><p>এতক্ষণ বকবক এর পর এখন আসি আমরা এলগরিদমেঃ</p><p>১। প্রথমে মূল গ্রাফের এজগুলোকে কস্টের/ ওয়েটের ভিত্তিতে ইনক্রিজিং অর্ডারে সর্ট করবো । যাতে করে আমরা মিনিমাম কস্টের / ওয়েটের এজকে পেতে পারি।</p><p>২। তারপর আমরা চেক করবো এই মিনিমাম কস্টের / ওয়েটের এজটি নেওয়ার ফলে আমাদের ট্রিতে কোন সাইকেল/লুপ তৈরি হয়ে যাচ্ছে কিনা । যদি লুপ/সাইকেল তৈরি হয় তাহলে সেই এজটা নিবোনা । অন্যথায় সেই এজটি আমাদের মিনিমাম স্প্যানিং ট্রিতে যুক্ত করবো।</p><blockquote>এই লুপ/সাইকেল আছে কিনা সেটা আমরা খুব সহজেই চেক করতে পারি <strong>Union Find</strong> ডাটা স্ট্রাকচার ব্যাবহার করে । যদি <a href="http://www.shafaetsplanet.com/?p=763"><strong>Union Find</strong></a><strong> </strong>সম্পর্কে আগে না জেনে থাকো তাহলে <a href="http://www.shafaetsplanet.com/?p=763"><strong>এখানে</strong></a> গিয়ে জেনে আসতে হবে।</blockquote><p>৩। ট্রি এর সংজ্ঞা অনুসারে যতক্ষন না n-1 পরিমান এজ আমাদের মিনিমাম স্প্যানিং ট্রিতে যুক্ত হচ্ছে ততক্ষন আমরা একই ভাবে আগাতে থাকবো।</p><p>এভাবে আমরা একটি গ্রাফ থেকে মিনিমাম স্প্যানিং ট্রি পেতে পারি।</p><p>উদাহরণঃ ( আমি অলস তাই নিজে কষ্ট করে চিত্র না একে <a href="https://www.geeksforgeeks.org/"><strong>geeksforgeeks</strong></a> থেকে উদাহরণ এবং চিত্র নিলাম)</p><p>মনে করি আমাদের একটি গ্রাফ দেওয়া আছে এমনঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/350/1*OtFHWpg_u4DlrAh0mMK-lg.jpeg" /></figure><p>এখন এই গ্রাফ থেকে আমরা মিনিমাম স্পেনিং ট্রি বিল্ড করবো । তাই আমাদের এলগরিদমের স্টেপ অনুযায়ী প্রথমেই সবগুলো এজকে কস্টের/ ওয়েটের ভিত্তিতে সর্ট করে নেই ।</p><pre>After sorting:<br>Src    Dest    Weight<br>7      6        1<br>8      2        2<br>6      5        2<br>0      1        4<br>2      5        4<br>8      6        6<br>2      3        7<br>7      8        7<br>0      7        8<br>1      2        8<br>3      4        9<br>5      4       10<br>1      7       11<br>3      5       14</pre><ul><li>এখন আমরা মিনিমাম ওয়েটের এজ 7← → 6 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটা নিবো আমরা ।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/120/1*oxU-BTgUT9LHWOp0bRMQ-g.jpeg" /></figure><ul><li>তারপর আমরা মিনিমাম ওয়েটের এজ 8← → 2 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো আমরা ।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/150/1*6TBUpsxzEgoV3sy_stCeNQ.jpeg" /></figure><ul><li>তারপর আমরা মিনিমাম ওয়েটের এজ 6← → 5 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/220/1*YxSorl1nQnvfXx0AcwaDxw.jpeg" /></figure><ul><li>তারপর আমরা মিনিমাম ওয়েটের এজ 0← → 1 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/260/1*bwkgj9hJqWgUZlyty5RN8w.jpeg" /></figure><ul><li>তারপর আমরা মিনিমাম ওয়েটের এজ 2← → 5 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*avDdHDMgGE9BKT2ixd2FlA.jpeg" /></figure><ul><li>এই মুহুর্তে আমাদের হাতে মিনিমাম ওয়েটের এজ হচ্ছে 8← → 6 যার ওয়েট 6 কিন্তু এই এজটা আমরা নিবোনা । কেননা, এই এজটাকে নিলে আমাদের গ্রাফে সাইকেল ক্রিয়েট হচ্ছে তাই আমরা এই এজটা স্কিপ করে পরের এজে চলে যাবো।</li><li>এখন আমরা মিনিমাম ওয়েটের এজ 2← → 3 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*ydfW5QxRoAY6Nu9CsV5LQw.jpeg" /></figure><ul><li>এখন আমাদের হাতে থাকা মিনিমাম ওয়েটের এজ 7← → 8 হলেও তা সাইকেল ক্রিয়েট করে তাই এটাকেও স্কিপ করবো আমরা।</li><li>এখন আমরা মিনিমাম ওয়েটের এজ 0← → 7যার ওয়েট 8কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/255/1*gN5a3kIlUkDUz5cUxmss5A.jpeg" /></figure><ul><li>এখন আমরা মিনিমাম ওয়েটের এজ 3← → 4 কে নিয়ে নিলাম । যা কোন সাইকেল তৈরি করে না , তাই এটাও নিবো।</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/280/1*E0zhPjmiLIe7yLuIRszPvQ.jpeg" /></figure><blockquote>এখন আমাদের দেওয়া গ্রাফের প্রতিটা n নোডকে এবং n-1 টি এজকে আমাদের মিনিমাম স্প্যানিং ট্রিতে যুক্ত করা হয়েছে তাই আমাদের এলগরিদম আর সামনে আগাবো না। কেননা, এখন আর যেকোন ওয়েটের যেকোন এজ যুক্ত করলেই গ্রাফে সাইকেল ক্রিয়েট হয়ে যাবে।</blockquote><p>এখন যে স্প্যানিং ট্রি আমরা পেয়েছি তার সবগুলো এজ এর যোগফল 37 যা মিনিমাম।</p><p>তাই এটিই আমাদের কাঙ্ক্ষিত <strong>মিনিমাম স্প্যানিং ট্রি । :)</strong></p><p>আশাকরি সবার এতক্ষণে সম্পুর্ন এলগরিদম কিলিয়ার হয়ে গেছে । যদি সমস্যা হয় তাহলে খাতা-কলমে আঁকা আঁকি করে দেখতে পারো।</p><h3>Code Implementation:</h3><ul><li>** প্রথমে গ্রাফ ইনপুট নিয়ে এজগুলো সর্ট করে নিবো । তারপর Union Find এর মাধ্যমে দেখবো এটা নিলে কি MST তে সাইকেল/লুপ হয়ে যাচ্ছে কিনা । কোডে কমেন্টে করে ইনফরমেশন এড করে দিয়েছি তাই আশাকরি সমস্যা হবে না।</li></ul><h3><strong>CODE:</strong></h3><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/ee316e5904df93ea0f9e65a52db1973a/href">https://medium.com/media/ee316e5904df93ea0f9e65a52db1973a/href</a></iframe><p><strong>Kruskal’s Algorithm Complexity :</strong></p><p>সবগুলো এজ সর্ট করতে Complexity O(<strong>E log E</strong>) + প্রতিটা এজ নিয়ে নিয়ে চেক করছি তার Complexity O(E).</p><p>Total : O(<strong>E log E</strong>)+O(<strong>E</strong>) = O(<strong>E log E</strong>).</p><p>আজকে এই পর্যন্তই । সামনে দেখা হবে Prim’s এলগরিদম নিয়ে । এবং দুইটা এলগরিদম এর মধ্যে পার্থক্য এবং কখন কোন এলগরিদম ব্যাবহার করবো তা নিয়ে লিখবো।</p><p>হ্যাপি কোডিং :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=74fda4b98638" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/kruskals-algorithm-minimum-spanning-tree-74fda4b98638">Kruskal’s Algorithm [ Minimum Spanning Tree ]</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Euler’s Phi Function [ Number Theory ]]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/eulers-phi-function-number-theory-2567168b5bc2?source=rss-81b552cf3066------2</link>
            <guid isPermaLink="false">https://medium.com/p/2567168b5bc2</guid>
            <category><![CDATA[number-theory]]></category>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[eulers-totient-function]]></category>
            <category><![CDATA[eulers-phi]]></category>
            <dc:creator><![CDATA[Masud Parves]]></dc:creator>
            <pubDate>Fri, 07 Dec 2018 04:07:57 GMT</pubDate>
            <atom:updated>2018-12-07T11:27:04.096Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*zuHYbVu4-Rq4mmOS" /><figcaption>Photo by <a href="https://unsplash.com/@antoine1003?utm_source=medium&amp;utm_medium=referral">Antoine Dautry</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>আজকে আমরা জানবো অয়লারের টশিয়েন্ট ফাংশন (<a href="https://en.wikipedia.org/wiki/Euler%27s_totient_function"><strong>Euler’s Phi Function</strong></a>) সম্পর্কে । যাকে প্রকাশ করা হয় φ(n) দিয়ে । আমরা φ(n)=x বলতে বুঝি 1 থেকে n অবধী x সংখ্যক সংখ্যা আছে যে সংখ্যা গুলো n এর সহমৌলিক (<strong>coprime</strong>) অর্থাৎ 1 থেকে n এর মধ্যে x সংখ্যক সংখ্যা আছে যাদের সাথে n এর GCD হবে 1.<br>যেমনঃ GCD(7,11)=1 তাই এরা সহমৌলিক (<strong>coprime</strong>)।</p><p><strong><em>উদাহরণঃ</em></strong> φ(24) = 8</p><p>কারণ -&gt;<br>GCD(1,24)=1, GCD(2,24)=2 , GCD(3,24)=3, GCD(4,24)=4 , GCD(5,24)=1, GCD(6,24)= 6 , GCD(7,24)=1, GCD(8,24)=8 ,<br>GCD(9,24)=3,GCD(10,24)=2, GCD(11,24)=1,GCD(12,24)=12,</p><p>GCD(13,24)=1, GCD(14,24)=2 , GCD(15,24)=3, GCD(16,24)=8 , GCD(17,24)=1, GCD(18,24)= 6 , GCD(19,24)=1, GCD(20,24)=4 ,<br>GCD(21,24)=3, GCD(22,24)=2, GCD(23,24)=1 , GCD(24,24)=24</p><p>এখানে মাত্র 8 টি সংখ্যা 24 এর সাথে কো-প্রাইম হিসেবে আছে তাই আমাদের φ(24) = 8 . একে অন্য ভাষায় বলা হয় <strong>number of </strong><a href="https://en.wikipedia.org/wiki/Totative"><strong>totatives</strong></a><strong> of n.</strong></p><blockquote>উপরের উদাহরণে একটা বেপার খেয়াল করি 12 জন্য কারা কারা বাদ পড়লো? 12 যাদের যাদের <strong>multiples </strong>হিসেবে আছে তারাই শুধুমাত্র বাদ পড়েছে তাই না? যেমনঃ 2, 3 , 4 , 6, 12 এর <strong>multiples </strong>12 তারা বাদ পড়েছে আর অতিরিক্ত বাদ পড়েছে 8 , 9 এবং 10 কেননা 8 , 10 দুইটা 2 এর <strong>multiples </strong>এবং 9 হচ্ছে 3 এর <strong>multiple</strong>.তাহলে আমরা বলতে পারি এখানে <strong>number of totatives of n is 4 where n</strong>=24.</blockquote><p><strong>Totient Function</strong> এর <strong>Brute Force</strong> বা কামলা কোডটি <a href="https://gist.github.com/Masud-Parves/27a7372079467956b4cfde1e32d17b17"><strong>এখানেই</strong></a></p><p>এখন আমরা একটা বেপার ভালোভাবে খেয়াল করলে দেখবো প্রতিটা প্রাইম নাম্বারের <strong>totative </strong>অর্থাৎ φ এর মান অবশ্যই ওই নাম্বার থেকে 1 কম । তাহলে, <br><strong>φ(n) = n-1</strong></p><p>যেখানে n একটি প্রাইম নাম্বার ।</p><p><strong><em>উদাহরণঃ</em></strong></p><p>n = 7 এর জন্যঃ</p><p>GCD(1,7)=1<br>GCD(2,7)=1<br>GCD(3,7)=1<br>GCD(4,7)=1<br>GCD(5,7)=1<br>GCD(6,7)=1<br>এবং<br>GCD(7,7)=7</p><p>φ(7) = 6</p><blockquote>এভাবে সকল প্রাইম নাম্বারের জন্য φ(n) = n-1 সমীকরণটি সত্যি । কেন তা হয়তো বুঝতে আর দেরি নেই সবার 🤓</blockquote><p>এখন আসি যখন n প্রাইম সংখ্যা হবে না তখন আমাদের সমীকরণটি কেমন হবে। ধরি আমাদের n একটি যৌগিক বা <strong>composite</strong> নাম্বার । এবং আমরা সবাই জানি যেকোন যৌগিক বা <strong>composite</strong> নাম্বারকে প্রাইম নাম্বারের গুনফল আকারে প্রকাশ করা যায় ( যেমনঃ <strong>10</strong> কে আমরা লিখতে পারি <strong>2¹*5¹</strong> এভাবে , <strong>24</strong> কে আমরা লিখতে পারি<strong> 2³ * 3¹</strong> এভাবে)</p><p>ধরি ,</p><p>m=p^k</p><p>(এখানে m আমাদের <strong>composite</strong> নাম্বার এবং p যেকোন প্রাইম নাম্বার)</p><p>এখন যে নাম্বার গুলোর m এর সাথে <strong>common factor</strong> হিসেবে থাকবে সেগুলো অবশ্যই p এর <strong>multiples</strong> হবে তাই না?</p><p>তাহলে আমরা বলতে পারি p এর <strong>multiples </strong>গুলো হচ্ছে এমনঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/299/1*FPzl7Ru1IscKD0fG_56qNg.png" /></figure><p>এখানে m এর সাথে <strong>common factors</strong> এর পরিমান হবে অবশ্যইঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/70/1*Zx_f2H2lpWH-Z_I4reC9wQ.png" /></figure><p>এখন তুমি বলবা আমি শুধু বলেই যাচ্ছি কিন্তু প্রমান দিচ্ছি না 😕। আসলে বেপারটা খুব সহজ চলো আবারও একটা উদাহরণ দেখিঃ</p><p>ধরি, m=2⁴<br>তাহলে m=2⁴=16 এর সাথে যে নাম্বার গুলোর <strong>common factors</strong> আছে সেগুলো 2, 2*2, 3*2 , 4*2 , 5*2 , 6*2, 2*7, 8*2 এর পরের গুলো ধরা হচ্ছে কেননা তা m=16 অতিক্রম করছে।<br>এখানে মোট <strong>common factors </strong>গুলোর পরিমান 2^(4–1)=8 তাই না? সব ঠিকঠাক 😛</p><p>তাহলে এখন মোট সংখ্যা থেকে<strong> common factors</strong> এর সংখ্যা বাদ দিলেই পেয়ে যাবো আমাদের কাঙ্ক্ষিত φ(m) এর মান ।</p><p>তাহলে ,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/261/1*hGJNdZ7pP8vi9mNjJYV7Ww.png" /></figure><p>এই সমীকরণকে আমরা ভেংগে লিখতে পারি,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/456/1*yX-6PahnKeATU2PLk-Dvuw.png" /></figure><blockquote>এখন যে সমীকরণটি আমরা পেলাম সেটা হলো যদি কোন নাম্বার একটি মাত্র প্রাইমের গুনফল আকারে থাকে সেটার জন্য । এখন আমাদের নাম্বারটি একধিক সংখ্যক প্রাইমের গুণফল আকারে প্রকাশ করতে হতে পারে । তাই সমীকরণটিকে <strong>generalized</strong> করতে হবে যাতে করে সব ক্ষেত্রে ওই সমীকরণ থেকে সঠিক সমাধান পেতে পারি।</blockquote><p>এখন আমরা যদি φ(n) এর মান বের করতে চাই যেখানে n হচ্ছেঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/297/1*kKYrLhRrPp4Cr9iOKSxp8w.png" /></figure><p><strong><em>এখানে p1 &lt; p2 &lt; … &lt; pr হচ্ছে প্রাইম নাম্বার এবং ki ≥ 1 যা প্রাইমের ঘাত ।</em></strong></p><p>তাহলে φ(n) এর জন্য সমীকরণটি হচ্ছে এমনঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/785/1*m3OKFpr46qJhT3Rnt4FWqQ.png" /></figure><p>বা,</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/476/1*b9Dk3sWYOhQPTX-Po4trfQ.png" /></figure><blockquote>এখানে p হচ্ছে মৌলিক সংখ্যা আর p|n মানে হচ্ছে সেইসব মৌলিক সংখ্যা যারা n কে নি:শেষে ভাগ করতে পারে। যেমন ধরো যখন আমরা লিখি a|b, এর মানে হচ্ছে a নি:শেষে ভাগ করতে পারে b কে। মানে, a হচ্ছে b এর ডিভিজর।</blockquote><p>যা অয়লারের প্রোডাক্ট ফরমুলা নামে পরিচিত ।</p><p>উদাহরণঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/742/1*Mc7Rr66i4tG7EzxBEUS7nA.png" /></figure><h3><strong>Euler’s Phi Coding:</strong></h3><p>আমরা <strong>Theorem</strong> এ দেখলা প্রতিবার প্রতিটা প্রাইমের জন্য যে পরিমান <strong>common factors</strong> বা <strong>multiples</strong> আছে তা মূল সংখ্যা থেকে প্রতিবার বিয়োগ করতে হবে ।</p><p>তাহলে 1 থেকে n এর মধ্যে কোন সংখ্যা p এর<strong> common factors</strong> বা <strong>multiples</strong> এর পরিমান জানা যায় কিভাবে?</p><p><strong>factor = n/p [</strong>যেখানে n হচ্ছে আমাদের প্রদত্ত নাম্বার যার Totient ভ্যালু বার করতে চাচ্ছি এবং p হচ্ছে প্রাইম নাম্বার গুলোর একটি ]</p><p>যেমনঃ</p><p>1 থেকে 10 এর মধ্যে 2 এর<strong> multiples</strong> সংখ্যা হচ্ছে 10/2=5 (যেমনঃ 2, 4, 6, 8, 10)</p><p>1 থেকে 10 এর মধ্যে 3 এর <strong>multiples</strong> সংখ্যা হচ্ছে 10/3=3 (যেমনঃ 3, 6, 9)</p><p>এখন আমরা ফিরে যাবো আমাদের φ(24) এর কাছে এবং দেখবো কিভাবে এটার উত্তর আমরা পেতে পারি।</p><p>24 কে প্রাইমের গুণফল আকারে লিখা যায় এভাবে 24 = (2³ * 3¹)</p><p>φ(24) এর সর্বোচ্চ মান হতে পারে 24 তাই এই 24 কে আমরা res এ এসাইন করবো।</p><p>res=24</p><p>24 এ প্রাইম সংখ্যা দুইটা → 2 এবং 3.</p><p>1 থেকে 24 এর মধ্যে 2-এর <strong>multiples </strong>বা <strong>common factors </strong>আছে কয়টি? উত্তরঃ 24/2=12টি এবং সেই সংখ্যা গুলো বাদ হয়ে যাবে (যা উপরে আমরা <strong>theorem</strong> এ জেনেছি) . তাহলেঃ</p><p>res=24–12=12</p><p>এখন n =24 কে 2 দিয়ে যতক্ষন ভাগ করা যায় করবো । (এখনে ভাগ করা যায় বলতে বোঝানো হয়েছে ভাগ করার ফলে ভাগশেষ শূন্য হওয়াকে)</p><p>n=24/2=12</p><p>n=12/2=6</p><p>n=6/2=3</p><p>এবার, 1 থেকে 12 এর মধ্যে 3-এর <strong>multiples</strong> আছে কয়টি? উত্তরঃ 12/3=4টি এবং সেই সংখ্যা গুলো বাদ হয়ে যাবে।</p><p>res=12–4=8</p><p>n=3 কে 3দিয়ে যতক্ষন ভাগ করা যায় করবো ।</p><p>n=3/3=1</p><p>এখানে n=1 হয়ে গেছে তাই কাজ এখানেই খতম । 😎</p><p>অবশেষে আমাদের res=8 যা আমাদের কাঙ্ক্ষিত উত্তর ।</p><p>কোন কনফিউশন থাকলে কোডটা দেখো আশাকরি পরিস্কার হয়ে যাবে।</p><p><strong>কোডঃ</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/c9f40de706a5a05b91feb983f5b09884/href">https://medium.com/media/c9f40de706a5a05b91feb983f5b09884/href</a></iframe><p><strong>আরও একটু Efficient Phi :</strong></p><p>এই পদ্ধতি ঠিক তখনই কাজ করবে যখন আমরা এটা জানি যে আমাদের অনেকবার টোশিয়েন্ট ফাংশনকে কল করা লাগবে। তখন আমরা টোশিয়েন্ট ফাংশনকে সিভের মত করে ইমপ্লিমেন্ট করবো। ছোট থেকে বড় প্রতিটা প্রাইমের জন্য ওই ইনডেক্সের টোশিয়েন্ট ভ্যালু আপডেট করবো।</p><p><strong>কোডটা দেখুনঃ</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0fe15263d41430073bedbf300fab2bd0/href">https://medium.com/media/0fe15263d41430073bedbf300fab2bd0/href</a></iframe><p>এই ছিলো আমাদের <strong>Euler’s Totient Phi Function.</strong> এই ফাংশটির অনেক এপ্লিকেশন আছে । হয়তো তা নিয়ে সামনে কোন একদিন লিখবো । আজ ছোট্ট একটি ট্রিক্সস বোনাস হিসেবে দিয়ে আজ শেষ করবো 😄। তা হচ্ছেঃ</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/461/1*bPD0XEP3wUJ_Rfk9bdusdg.png" /></figure><p>তার মানে হচ্ছে যদি একটা প্রাইমের দুই বা তার অধিক ঘাত হিসেবে কোন সংখ্যা প্রকাশ করা যায় তাহলে তার জন্য Totient Phi আমরা খুব সহজেই বের করে ফেলতে পারি।</p><p>যাওয়ার আগে শেষ উদাহরণঃ</p><p>φ(343)=φ(7³)</p><p>=&gt; 7²*φ(7)</p><p>=&gt;7² * (7–1) = 294</p><p>উত্তরটা মিলিয়ে দেখতে পারো ।</p><p>হ্যাপি কোডিং 😊</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=2567168b5bc2" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/eulers-phi-function-number-theory-2567168b5bc2">Euler’s Phi Function [ Number Theory ]</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Segmented Sieve [ Number Theory ]]]></title>
            <link>https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/segmented-sieve-number-theory-1af0602dba39?source=rss-81b552cf3066------2</link>
            <guid isPermaLink="false">https://medium.com/p/1af0602dba39</guid>
            <category><![CDATA[competitive-programming]]></category>
            <category><![CDATA[segmented-sieve]]></category>
            <category><![CDATA[সেগমেন্টেড-সিভ]]></category>
            <category><![CDATA[bangla]]></category>
            <category><![CDATA[number-theory]]></category>
            <dc:creator><![CDATA[Masud Parves]]></dc:creator>
            <pubDate>Tue, 27 Nov 2018 07:44:23 GMT</pubDate>
            <atom:updated>2018-12-02T19:44:10.218Z</atom:updated>
            <content:encoded><![CDATA[<figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/0*C-tsXWJdChUBdBRO" /><figcaption>Photo by <a href="https://unsplash.com/@grohsfabian?utm_source=medium&amp;utm_medium=referral">Fabian Grohs</a> on <a href="https://unsplash.com/?utm_source=medium&amp;utm_medium=referral">Unsplash</a></figcaption></figure><p>আজ আমরা Segmented Sieve সম্পর্কে জানবো। Segmented Sieve এর আরেক নাম Segmented Sieve of Eratosthenes । সেগমেন্টেড সিভ (Segmented Sieve) সম্পর্কে জানতে হলে আমাদের আগে জানতে হবে Sieve এলগোরিদম সম্পর্কে যা “Sieve of Eratosthenes” নামে পরিচিত। Sieve of Eratosthenes নিয়ে অনেক ভালো ভালো ব্লগ বাংলায় আছে তাই এটা নিয়ে নতুন করে কিছু লিখবো না। আমরা সরাসরি চলে যাবো Segmented Sieve এ।</p><p>Segmented Sieve: এলগরিদমের নাম অনুসারেই নির্দিষ্ট সেগমেন্ট বা রেঞ্জ এর মধ্যে প্রাইম নাম্বার জেনারেট করার জন্য খুব কার্যকরী একটা এলগরিদম এই Segmented Sieve.</p><p><strong>সমস্যাঃ যদি আমাদের L এবং R এর একটি রেঞ্জ দেওয়া থাকে এবং বলা হয় L এবং R এর মধ্যবর্তী সকল প্রাইম নাম্বার প্রিন্ট করতে তখন আমরা কি করব? (যেখানে Constraints হচ্ছে 1&lt;=L&lt;=R&lt;=10¹⁰, R-L &lt;= 10⁵)<br>যেমন ধরুন আপনাকে কেউ প্রশ্ন করল “29 থেকে 700 পর্যন্ত কোন কোন নাম্বার প্রাইম আছে?” তা প্রিন্ট করো।</strong></p><p>আমরা তো “Sieve of Eratosthenes” এর মাধ্যমে Global Array ব্যাবহার করে সর্বোচ্চ 10⁸ পর্যন্ত প্রাইম নাম্বার জেনারেট করতে পারবো।কিন্তু এখানে আমরা 10¹⁰ সাইজের এতো বড় Array তো Declare করতে পারবো না 🤔। তাহলে এখন আমাদের কি হবে? 😥</p><blockquote>আমরা Sieve এলগোরিদম এর সাথে আমাদের কিছু Observations কে কাজে লাগিয়ে Segmented Sieve টা করে ফেলবো।</blockquote><p>Lets বেগুন 😂</p><p>★★ Sieve এলগোরিদমে আমরা যদি 100 অবধি প্রাইম নাম্বার জেনারেট করতে চাইতাম তাহলে কি করেছিলাম?<br> <br>sqrt(100)= 10 অবধী লুপ চালিয়ে এক একটা Element কে ধরে তার Multiples গুলোকে কেটে দিয়ে ছিলাম তাই না?</p><p>যেমনঃ প্রথমে 2 কে ধরে তার Multiples 2,4,6…. সবগুলো কেটেছি।<br> <br>তারপর 3 কে ধরেছি তার Multiples 6,9,12,15…. সবগুলো কেটেছি। এভাবে ১০ অবধী সকল নাম্বারকে ধরে তার Multiples গুলো কাটার পর আমাদের কাছে অবশিষ্ট যে নাম্বারগুলো ছিলা সেগুলো Prime. তাই না?<br> <br>এখানে আমরা ঠিক তাই করবো। 10¹⁰ অবধী প্রাইম নাম্বার পেতে হলে আমাদের sqrt(10¹⁰)= 10⁵ অবধী সবগুলো প্রাইম নাম্বার জেনারেট করে নিবো।<br> <br>তারপর আমরা প্রতিটা প্রাইম নাম্বারকে ধরবো এবং আমাদের দেওয়া সেগমেন্ট বা রেঞ্জের মধ্যে ওই প্রাইমের Multiples গুলো কাটবো।<br> <br>যেমনঃ ধরি আমাদের L=29 থেকে R=700 অবধী প্রাইম নাম্বার জেনারেট করতে হবে।<br> <br>তাহলে sqrt(700)= 26.4575 ~ 27 অবধী প্রাইম নাম্বার Sieve এর মাধ্যমে জেনারেট করে নিবো৷<br>1 থেকে 27 এর প্রাইম নাম্বার হচ্ছে 2,3,5,7,11,13,17,19,23।<br> <br>এখন আমরা 2 কে ধরবো এবং আমাদের সেগমেন্টের মধ্যে 2 এর জন্য composite নাম্বার মার্ক করবো বা কেটে দিবো। একই ভাবে 3,5,7 ইত্যাদি সকল প্রাইমকে দিয়ে আমাদের সেগমেন্ট বা রেঞ্জের মধ্যে ওই প্রাইমের জন্য Composite নাম্বার কেটে দিবো। তাহলে ফাইনালি আমাদের সেগমেন্টে অবশিষ্ট যে নাম্বারগুলো থাকবে তা অবশ্যই প্রাইম ☺।</p><ul><li><strong>*এখন কথা হচ্ছে সেগমেন্টের ভিতরে বিভিন্ন প্রাইমের জন্য প্রথম Composite নাম্বার কোনটা যা আমরা প্রথমে মার্ক করবো বা কাটবো?</strong></li></ul><p>যেমনঃ</p><p>আমাদের হাতে জেনারেট করা ,১ম প্রাইম 2 এর জন্য আমরা কাটা শুরু করবো কত থেকে? অবশ্যই 4 থেকে নয়, কেননা এইগুলা তো Sieve এর মাধ্যমে আগেই কাটা হয়ে গেছে। তাই আমরা এখন শুধুমাত্র সেগমেন্টের ভিতরের Composite নাম্বারগুলো কাটবো।<br> <br>প্রতিটা প্রাইম নাম্বারের জন্য যে নাম্বারটি আমরা প্রথমে কাটবো (যা আমরা base ধরলাম) তা পাওয়ার সুন্দর একটা ফরমুলা আছে। যা নিম্নে দিলাম।<br> <br><strong><em>base = curPrime*curPrime;</em></strong><br> <br>(এখানে curPrime বলতে আমি বুঝিয়েছি 2, 3,5… ইত্যাদি প্রাইম নাম্বারগুলো যা আমরা আগেই Sieve এর মাধ্যমে জেনারেট করেছি)<br> <br>এখন কথা হচ্ছে base এর মান যদি আমাদের সেগমেন্টের শুরু L থেকে ছোট হয়, তাহলে শুধু কারেন্ট প্রাইম এর বর্গ করলে হবে না। যেমন ২ এর বর্গ ৪, কিন্তু আমাদের L=29 যেটা এখনও অনেক দূরে। তখন base বা রেঞ্জের মধ্যে প্রথম Composite খুজে পাবো ছোট একটা কন্ডিশনের মাধ্যমে।</p><p><strong><em>if(base &lt; L)<br>base = ( ( L + curPrime — 1 ) / curPrime ) * curPrime;</em></strong></p><p><strong>প্রশ্নঃ কিভাবে এই ফর্মুলা আসলো?</strong></p><p><strong>উত্তরঃ</strong></p><p>ধরুন আপনাকে জিজ্ঞেস করা হলো –<br>“19 এর সমান বা ছোট কোন সংখ্যাটা 3 দ্বারা নিঃশেষে বিভাজ্য?” [ Ans: 18 ]<br>“19 এর সমান বা বড় কোন সংখ্যাটা 3 দ্বারা নিঃশেষে বিভাজ্য?” [ Ans : 21 ]<br>কিভাবে পেলাম?<br>19/3 এর ভাগফল 6, এটাকে আবার 3 দিয়ে গুন করলে 18। এটা আমাদের ১ম প্রশ্নের উত্তর।<br>19/3 এর ভাগফল 6, এর সাথে অতিরিক্ত 1 + করে পাই (7/7)*3 = 21 যা আমাদের ২য় প্রশ্নের উত্তর।</p><p>১ম উপায় ঠিক ভাবে কাজ করলেও ২য় টি ভুল উত্তর দিবে যদি প্রশ্নে 19 এর বদলে 21 দেয়া থাকে।<br>মানে যদি হর দ্বারা লব নিঃশেষে বিভাজ্য হয় তখন ভুল উত্তর আসবে।<br>21 এর জন্য ১ম উত্তর আসবে 21 [ যা ঠিক ] , কিন্তু ২য় উত্তর আসবে 24 [ যা ভুল, সঠিক উত্তর 21 ]<br>তাহলে কি করা যায়?<br>আমরা আমাদের ২য় ফর্মুলা একটু এদিক ওদিক করব যেন সেটা সবসময় ঠিক উত্তর দিতে পারে।<br>আমরা 21 ( লব ) থেকে 1 বিয়োগ করব আর 3 ( হর ) যোগ করে নিব।<br>মানে ( 21–1 +3 ) = 23।<br>23/3 এর ভাগফল (7/7)*3 = 21 যা আমাদের উত্তর।<br>এটাই উপরের ফর্মুলার রহস্য!</p><p><strong>এখন দুইটা উদাহরণ দেখা যাকঃ</strong><br> <br>প্রথম প্রাইম 2 এর জন্য রেঞ্জের ভিতর প্রথম Composite মার্ক হবে এভাবে,<br> <br><strong><em>base = 2*2;</em></strong><br> <br>যা আমাদের সিগমেন্টের L = 29 থেকে ছোট তাই</p><p><strong><em>base= ((29+2–1)/2)=15*2=30</em></strong><br> <br>তাহলে প্রথম<strong> Composite</strong> কাটবো 30 এবং তারপর R অবধি 2 এর সকল <strong>Multiples </strong>কাটবো।<br> <br>তাহলে 2 এর জন্য রেঞ্জের ভিতরে কাটা যাবে বা <strong>Composite</strong> মার্ক হবে 30,34,36,38…. এভাবে R=700 অবধী।<br> <br>২য় প্রাইম 3 এর জন্য একই ভাবে কাটা যাবে 33,36,39… এভাবেই রেঞ্জ R=700 অবধী।<br> <br>তাহলে একই ভাবে sqrt(700)= 26.4575 ~ 27 এর আগে যত প্রাইম আছে সবগুলোর জন্য <strong>Composites</strong> কাটবো বা মার্ক করবো।<br> <br><strong><em>★★ এখন আসি আমরা Array Deceleration এ। আমাদের সেগমেন্ট বা রেঞ্জ এর ভ্যালু R সর্বোচ্চ 10¹⁰ হতে পারে। তাহলে আমরা এতো বড় সাইজের Array কিভাবে Declare করবো? এতো বড় সাইজের Array Declare করা তো অসম্ভব,তাহলে উপায়?😧😢</em></strong><br> <br>আসলে আমাদের এতো বড় সাইজের Array নিতেই হবে না। কেননা, আমাদের Constraints এ বলা আছে R-L = 10⁵ এবং আমরা শুধুমাত্র 10⁵ সাইজের Array Declare করলেই চলবে। শুধুমাত্র Index গুলো ম্যাপ করবো সিম্পল 😋।</p><p>যেমনঃ<br>আমাদের উদাহরণ অনুযায়ী যদি L=29 এবং R=700 হয়, তাহলে Array নিবো R-L সাইজের।<br> <br><strong><em>int isPrime [ R — L + 1 ];<br> </em></strong><br>এখানে আমরা,<br> <br><strong><em>isPrime[0]</em></strong> মানে বুঝবো <strong><em>29</em></strong><br><strong><em>isPrime[1]</em></strong> মানে বুঝবো <strong><em>30</em></strong><br><strong><em>isPrime[2]</em></strong> মানে বুঝবো <strong><em>31</em></strong><br>.<br>.<br>.<br>.<br><strong><em>isPrime[R-L]</em></strong> মানে বুঝবো <strong><em>700</em></strong><br> <br>এবং যদি আমাদের প্রাইম নাম্বার প্রিন্ট করতে বলা হয় তখন <strong><em>L+index</em></strong> প্রিন্ট করে দিবো।<br>এভাবেঃ<br> <br><strong><em>if ( isPrime[i] == true )<br>cout &lt;&lt; L+i &lt;&lt; endl;</em></strong></p><p>যেমনঃ<br> <br><strong><em>31</em></strong> মানে আমাদের কাছে <strong><em>isPrime[2]</em></strong>. প্রোগ্রামার শেষে আমরা <strong><em>isPrime[2]=true</em></strong> পাবো, কেননা <strong><em>31 </em></strong>একটি প্রাইম নাম্বার।তাহলে <strong><em>L+index = 31</em></strong> হয়।<br> <br>একটা কথা মাথায় রাখতে হবে আমাদের যদি<strong><em> L=1 </em></strong>তাহলে <strong><em>isPrime[0]=false</em></strong> হবে, কেননা <strong><em>1 </em></strong>প্রাইম নাম্বার না।<br> <br>এখন ঝামেলা মনে হলে, লিখাটা আরেকবার পড়ো। এবং আশাকরি নিচের কোডের <strong>Implementation</strong> দেখলে ক্লিয়ার হয়ে যাবে।<br>[ সাথে ১টা স্প্রাইট রাখতে পারেন ;) ]</p><p><strong>কোডঃ</strong></p><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/0aa799e94abd7045182c3cba9cea8de9/href">https://medium.com/media/0aa799e94abd7045182c3cba9cea8de9/href</a></iframe><iframe src="" width="0" height="0" frameborder="0" scrolling="no"><a href="https://medium.com/media/01d166c269081f1ddb5bbc823aeb68a5/href">https://medium.com/media/01d166c269081f1ddb5bbc823aeb68a5/href</a></iframe><blockquote>সম্পুর্ন কোডের লিংকঃ <a href="https://gist.github.com/Masud-Parves/1779857367110c2d86835cbe5a782f42"><strong><em>Segmented Sieve Full Code</em></strong></a></blockquote><p>একটু ভেংগে লিখতে গিয়ে হয়তো লিখাটা একটু বড় হয়ে গেছে। কোথাও কোন প্রশ্ন থাকলে অবশ্যই জানাবেন।</p><p>আজ এই পর্যন্তই রইলো । সামনে কোন একদিন অন্যকোন টপিক্স নিয়ে লিখবো আশা করি ।</p><p>★★ আমার লিখার Inspirations পেয়েছি Md Shahidul Islam ভাই এবং Shakil Ahmed ভাই এর কাছে থেকে।</p><p>Happy Coding :)</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=1af0602dba39" width="1" height="1" alt=""><hr><p><a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE/segmented-sieve-number-theory-1af0602dba39">Segmented Sieve [ Number Theory ]</a> was originally published in <a href="https://medium.com/%E0%A6%AA%E0%A7%8D%E0%A6%B0%E0%A7%8B%E0%A6%97%E0%A7%8D%E0%A6%B0%E0%A6%BE%E0%A6%AE%E0%A6%BF%E0%A6%82-%E0%A6%AA%E0%A6%BE%E0%A6%A4%E0%A6%BE">প্রোগ্রামিং পাতা</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Divisibility Rule || UVa 11344 — The Huge One]]></title>
            <link>https://medium.com/@masudparves/divisibility-rule-uva-11344-the-huge-one-de2106f84515?source=rss-81b552cf3066------2</link>
            <guid isPermaLink="false">https://medium.com/p/de2106f84515</guid>
            <category><![CDATA[techniques]]></category>
            <category><![CDATA[divisible]]></category>
            <category><![CDATA[divisibility-rule]]></category>
            <category><![CDATA[tutorialsbangla]]></category>
            <dc:creator><![CDATA[Masud Parves]]></dc:creator>
            <pubDate>Sat, 03 Nov 2018 18:05:19 GMT</pubDate>
            <atom:updated>2018-11-03T18:05:19.292Z</atom:updated>
            <content:encoded><![CDATA[<h3>Divisibility Rule || UVa 11344 — The Huge One</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*wSCJ-FoX37odZwZV9LMkEA.jpeg" /></figure><p>PROBLEM : UVa 11344 The Huge One<br>LINK : <a href="https://uva.onlinejudge.org/index.php?option=com_onlinejudge&amp;Itemid=8&amp;page=show_problem&amp;problem=2319">UVa 11344 The Huge One</a></p><p>Descriptions : প্রবলেমে বলা হয়েছে, তোমাকে একটা নাম্বার M দিবে এবং একটি সেট S দিবে, যেখনে S এর ভিতর 1–12 পর্যন্ত কিছু সংখ্যা থাকবে৷ <br>তোমাকে বলতে হবে সেট S এ যে সংখ্যাগুলো দেওয়া আছে তাদের সবগুলো নাম্বার দিয়ে উপরের M কে ভাগ করা যায় কিনা (এখনে ভাগ করা যাওয়া মানে হচ্ছে ভাগশেষ শূন্য হবে কিনা বোঝানো হয়েছে)। যদি সেট S এর সব গুলো সংখ্যা দিয়ে ভাগ যায় তাহলে প্রিন্ট করতে হবে M — Wonderful. (M এখানে হচ্ছে প্রদত্ত নাম্বার) অন্যথায় M — Simple. প্রিন্ট করতে হবে।</p><p>এই ছিলো প্রবলেম, এখন সমস্যা হচ্ছে CONSTRAINTS এ দেওয়া আছে 0&lt;=M&lt;=10¹⁰⁰⁰ 😥.</p><p>যেহেতু আমি বিগ নাম্বার দেখলেই ভয় পাই, সেই সুবাধে মাথায় চক্কর দিলো 😓।</p><p>যেহেতু আমি বিগেনার প্রোগ্রামার, ভাবলাম মোড করে না হয় চেক করবো, কিন্তু এতো বড় নাম্বার store করবো কিভাবে।</p><p>দুইদিন ঝিমানোর পরে দুইটা উপায় পেলাম ☺.</p><p>আজ সেই দুইটা এপ্রোজ নিয়েই কথা হবে ☺.</p><p>Lets বেগুন 😛</p><p>Approach One : (অনেক বড় নাম্বার হওয়া M আমাদের string এ নিতে হবে)</p><p>প্রথম উপায়টা একদম সহজ, Modular Arithmetic Approach.</p><p>Modular Arithmetic নিয়ে ডিটেইল আলোচনা করবো না, কেননা এ নিয়ে বাংলা এবং ইংরেজিতে অনেক ভালো ভালো লেখা আছে।</p><p>শাফায়াত ভাইতের সোনার টুকরার লেখাটা পড়ে আসতে পারোঃ<a href="http://www.shafaetsplanet.com/?p=936"> মডুলার অ্যারিথমেটিক</a></p><p>এই প্রবলেম সলিউশন এর জন্য সাধারন সমিকরণ টা হবে এমন ঃ a*10%m=((a%m)*10)%m</p><p>এই approach টি নাম্বারের প্রথম থেকে (বাম পাশ থেকে) শেষ অবধী লুপের মাধ্যমে প্রতিটা ডিজিটের জন্য এপ্লাই হবে। এবং সেটা অবধ্যই সেট S এর প্রতিটা নাম্বারের জন্য৷</p><p>সমিকরণে a দিয়ে বোঝানো হয়ে বামদিক থেকে প্রতিটা ডিজিট এবং m হচ্ছে সেটের প্রত্যেক এলিমেন্ট।</p><p>আশাকরি, শাফায়াত ভাই এর ব্লগ পড়ে থাকলে এবং উপরুক্ত সমিকরণটি কেন কাজ করছে তা বুঝতে পেরেছো। যদি তবুও না বুঝে থাকো তাহলে আবার পড় এবং খাতা কলমে একটু দাগাদাগি করো। 🙂</p><p>এখনো পাড়ছো না? 😕 <br>নিচের সলিউশনটা দেখো এবং বুঝর চেষ্টা করো।</p><h4>Solution One Code : <a href="https://paste.ubuntu.com/p/ZvKmZXyBmp/">https://paste.ubuntu.com/p/ZvKmZXyBmp/</a></h4><blockquote>[বিঃদ্রঃ কোড কপি পেষ্ট করে শুধুমাত্র Accepted কোডের সংখ্যা না বাড়িয়ে, কোডটি বুঝে নিজের মেধাকে বাড়াও ]</blockquote><p>Approach Two :</p><p>এখন আসি আমার পছন্দের এবং মজার approach এ 😍.</p><p>এটাও খুব সহজ একটা approach 😋.</p><p>স্বভাবতই, আমরা string এ ইনপুট নিবো।</p><p>এখন একটা বেপার খেয়াল করা যাক। আমাদের যে নাম্বর গুলো দিয়ে প্রতিবার ভাগ যায় কিনা চেক করতে হচ্ছে তা কিন্তু ফিক্সড যা অবধ্যই 1 থেকে 12 এর মধ্যেই।</p><p>এখন আমরা যদি (M) কোন সংখ্যা দেখে চট করে বলে দিতে পারি যে, এই সংখ্যাটি কি আমাদের সেটের সংখ্যা দিয়ে ভাগ যায় কিনা তাহলেই তো হয়ে গেলো। ভাগ করে দেখার তো দরকার নাই তাই না?</p><p>হ্যা, এবং আমরা সেটাই করবো। আমরা প্রথম সহজ কিছু উপায় শিখবো যাতে করে বলতে পারি কোনো সংখ্যা কোন কোন সংখ্যা দিয়ে ভাগ যায় কি না। তাহলেই তো আমরা এই প্রবলেমটা থেকে হাত ছেড়ে বাচতে পরি।</p><p>তাহলে আমরা 1 থেকে 12 এর সবগুলো নাম্বারের জন্য Divisibility Rules গুলো দেখবোঃ</p><p>1 এর জন্য রুলঃ <br>1 তো বেচরা নাম্বার 😛 এটা দিয়ে দুনিয়ার সব নাম্বার কে ভাগ করা যায়।</p><p>2 এর জন্য রুলঃ<br>আমরা জানি, 2 শুধু মাত্র জোড় সংখ্যকে ভাগ করতে সক্ষম। <br>এবং এটাও জানি, কোন সংখ্যার শেষের ডিজিটি জোড় মানে পুরো সংখ্যটি জোড়।</p><p>যেমনঃ 1678936 এই সংখ্যা দিয়ে বিভাজ্য কারন এর শেষের 6 জোড় সংখ্যা যা দুই দিয়ে ভাগ যায়।</p><p>3 এর জন্য রুলঃ <br>কোন নাম্বারের প্রতিটা ডিজিটের যোগফল যদি 3 দিয়ে ভাগ যায়। তাহলে সেই সংখ্যাটি অবধ্যই ৩দিয়ে বিভাজ্য 🙂।</p><p>যেমনঃ 123639 এই সংখ্যাটির ডিজিট গুলোর যোগফলঃ 1+2+3+6+3+9 = 24 যা 3 (24%3=8) দিয়ে বিভাজ্য । তাই পুরো সংখ্যাটি 3 দিয়ে বিভাজ্য।</p><p>4 এর জন্য রুলঃ</p><p>কোন সংখ্যার শেষের দুইটি সংখ্যা যদি 4 দিয়ে বিভাজ্য হয় তাহলে সেই পুরো সংখ্যাটি 4 দ্বারা বিভাজ্য হবে।</p><p>যেমনঃ 1226732432 এখনে শেষে দুইটি সংখ্যা 32 যা 4 (32÷4=8) দ্বারা বিভাজ্য.</p><p>5 এর জন্য রুলঃ কোন সংখ্যার শেষের ডিজিট 0 অথবা 5 থাকলে সেই সংখ্যাটি অবশ্যই 5 দ্বারা বিভাজ্য হবে।</p><p>যেমনঃ 15727775 এবং 165378390</p><p>6 এর জন্য রুলঃ <br>কোন সংখ্যা যদি 2 দ্বারা এবং 3 দ্বারা যৌথ ভাবে বিভাজ্য হয়, তাহলে ওই সংখ্যাটি অবশ্যই 6 দ্বারা বিভাজ্য হবে।</p><p>যেমনঃ 72665412 সংখ্যাটি উপরের রুল অনুযায়ী 3 এং 2 উভয় সংখ্যা দ্বারা বিভাজ্য তাই সংখ্যাটি 6 দ্বারা অবশ্যই বিভাজ্য।</p><p>7 এর জন্য রুলঃ <br>7 এর জন্য অনেক গুলা রুলস আছে। যেমনঃ কোন নাম্বারে প্রাইম ফ্যক্টরাইজেশনে প্রাইম ফ্যাক্টর হিসাবে 7 থাকলে সেটা 7 দ্বারা বিভাজ্য৷</p><p>হায় হায় কি হইলো? এখন এতো বড় নাম্বারের প্রাইম ফ্যাক্টরাইজেশন করবো কিভাবে? 😭</p><p>কান্নার কিছু নাই, বলেই তো দিয়েছি অনেক গুলা রুলস আছে। তাহকে সবচাইতে সহজ নিয়ম টা হলোঃ</p><p>যে নাম্বারটা দেওয়া থাকবে সেই সংখ্যাটার শেষ থেকে ৩টা করে নাম্বর নিয়ে একটা গ্রুপ করবো। <br>যদি নাম্বারটা দেওয়া থাকে 6913580247</p><p>১ম গ্রুপঃ 247<br>২য় গ্রুপঃ 580<br>৩য় গ্রুপঃ 913<br>৪র্থ গ্রুপঃ 6 ( একটা ডিজিট অবশিষ্ঠ আছে তাই, বেশী থাকলে সেটাই লিখতাম)</p><p>এখন ১ম গ্রুপকে যোগ, ২য় গ্রুপে বিয়োগ, ৩ গ্রুপ কে যোগ, ৪র্থ গ্রুপ কে বিয়োগ করবো। যতগুলো গ্রুপ থাককনা কেন একই ভাবে আগাবো।</p><p>মোট যে সংখ্যা হবে, তা যদি 7 দিয়ে বিভাজ্য হয় তাহলে মোট সংখ্যাটাও 7 দিয়ে বিভাজ্য হবে৷</p><p>যেমনঃ উদাহরণ টাই শেষ করি</p><p>+247<br>-580<br>+913<br>- 6<br>[আমরা ধারার ন্যায় চিন্তা করতে পাড়ি <br>247–580+980–6 = 574]</p><p>total sum : 574 যা 7 (574÷7=82) দ্বারা বিভাজ্য তাই 6913580247 সংখ্যাটি 7 দ্বারা অবশ্যই বিভাজ্য।</p><p>অনেকেই হয়তো প্রতিবার এই শেষের 3টা ডিজিট নিয়ে গ্রুপ করা তারপর যোগ বিয়গ করা নিয়ে চিন্তায় পরে গেছো। আসলে বেপারটা সিম্পল। চিন্তা করো পেয়ে যাবা। 🙂</p><p>8 এর জন্য রুলঃ কোন সংখ্যার ৩টা ডিজিট যদি 8 দ্বারা ভাগ যায় তাহলে সেই সংখ্যাটা অবশ্যই 8 দ্বারা ভাগ যায়।</p><p>যেমনঃ 6913580248 নাম্বারের শেষের ৩টা ডিজিট 248 যা 8 দ্বারা বিভাজ্য তাই পুরো সংখ্যাটি অবধ্যই 8 দ্বারা বিভাজ্য।</p><p>9 এর জন্য রুলঃ <br>কোন সংখ্যার প্রতিটা ডিজিটের যোগফল যদি 9 দ্বারা বিভাজ্য হয় তাহলে সম্পুর্ণ সংখ্যাটি 9 দ্বারা বিভাজ্য। ( অনুরুপ 3 এর রুল এর মত)</p><p>যেমনঃ 1236393 এর প্রতিটা ডিজিটের যোগফলঃ 1+2+3+6+3+9+3=27 যা 9 দ্বারা (27÷9=3) বিভাজ্য।সুতরাং সম্পুর্ণ সংখ্যাটি 9 দ্বারা বিভ্যাজ।</p><p>10 এর জন্য রুলঃ <br>যে সংখ্যার শেষের ডিজিট 0 কেবল মাত্র সেই সংখ্যাগুলোই 10 দ্বারা বিভাজ্য।</p><p>11 জন্য রুলঃ <br>প্রতিটা সংখ্যাকে একটি গ্রুপ ধরে ( 7 এর মত কিছুটা) প্রথম থেকে ডিজিট গুলো পর্যায়ক্রমে যোগ, বিয়োগ করতে থাকবো। সম্পুর্ন ফলাফল যদি 11 দ্বারা বিভাজ্য হয় তাহলে সম্পুর্ণ নাম্বারটি 11 দ্বারা বিভাজ্য।</p><p>যেমনঃ 145816 সংখ্যাটির জন্য প্রতিটা সংখ্যাকে গ্রুপ ধরলে এরুপ হবেঃ</p><p>1–4+5–8+1–6= -11 যা 11 দ্বারা বিভাজ্য (-11%11=0) তাই সম্পুর্ণ সংখ্যাটি 11 দ্বারা বিভাজ্য।</p><p>12 এর জন্য রুলঃ <br>কোন সংখ্যা যৌথ ভাবে 3 এবং 4 দিয়ে বিভাজ্য হলে সংখ্যাটি অবশ্যই 12 দ্বারা বিভাজ্য।</p><p>যেমনঃ 144 যা উপরুক্ত রুলস অনুসারে 3 এবং 4 দ্বারা বিভাজ্য তাই সংখ্যাটি অবশ্যই 12দ্বারা বিভাজ্য।</p><p>অবশেষে অনেক বকবকানির পরে 1 থেকে 12 জন্য Divisible রুল আমরা জানলাম। এখন প্রতিটা সংখ্যার জন্য যদি একটা করে ফাংশন তৈরী করি তাহলেই কাজ শেষ। ☺</p><p>এতোক্ষনে সবার প্রবলেমটি Accepted হয়ে যাওয়ার কথা। যদি না হয়ে থাকে, নিচের Solution এ একটু চোখ বুলিয়ে আসো। তারপর কোডটা নিজে করো।</p><h4>Solution Code Two: <a href="https://paste.ubuntu.com/p/XdMf2kRj3H/">https://paste.ubuntu.com/p/XdMf2kRj3H/</a></h4><ul><li>এইটাই আমার প্রথম নোট কিংবা ব্লগ লিখা। আশা করি সামনে আরও লিখবো। আমার লেখার ইন্সপারেশন <a href="https://web.facebook.com/Shahidul.BRUR">Md Shahidul Islam</a> ভাই, <a href="https://web.facebook.com/shakil.ahmed.980">Sakil Ahmed </a>ভাই।</li></ul><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=de2106f84515" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>