Minimum Stack Problem

Minimum Stack সমস্যাটি একটি অত্যন্ত পরিচিত সমস্যা। আমি এমনও শুনেছি software engineering এর job এর coding interview তে এই সমস্যা সমাধান করতে দেওয়া হয়েছে। এই সমস্যা এবং এর সমস্যা নিয়ে আমরা এখন আলোচনা করব। 

নাম শুনেই আমরা অনুমান করতে পারতেছি যে এটি একটি stack data structure সংক্রান্ত সমস্যা । এই সমস্যায় আমাকে একটি stack দেওয়া থাকবে। এর সাথে আমাদেরকে দুই ধরনের operation এবং দুই ধরনের query দেওয়া হবে। দুই ধরনের operation গুলো হল push ও pop. Push operation এর মাধ্যমে আমাকে stack এ একটি integer push করতে হবে আর pop operation এর মাধ্যমে আমাকে stack এর উপর থেকে একটি integer তুলে নিতে হবে। আবার দুই ধরনের query এর মধ্যে একটি হচ্ছে আমাদেরকে বলতে হবে stack এ আপাতত সবার উপরে থাকা integer এর value কত এবং অপরটি হচ্ছে আপাতত stack এ থাকা integer গুলোর মধ্যে সব থেকে ছোট integer এর value কত । আরেকটি ব্যাপার হচ্ছে আমাদের memory complexity অবশ্যই O(n) হতে হবে। 

আমরা STL stack ব্যবহার করে খুব সহজেই উপরের দুইটি operation এবং প্রথম query এর সমাধান করতে পারি । এখন বাকি থাকে তাহলে দ্বিতীয় ধরনের query. এর জন্য আমরা যেটি করব যে, stack এ আমারা pair<int,int> type এর data রাখবো যেখানে প্রথম integer হচ্ছে stack এ আমরা যেসব element push বা pop করতেছি, আর দ্বিতীয় integer হচ্ছে ওই position থেকে শুরু করে আপাতত stack এর নিচের দিকে শেষ পর্যন্ত যেসকল integer আছে তাদের মধ্যে সব থেকে ছোট integer টি । অর্থাৎ আমরা দ্বিতীয় ধরনের query এর answer হবে  আপাতত stack এর উপরে যে pair of integer আছে তার মধ্যে দ্বিতীয়টি। এটি বের করার জন্য আমাদেরকে শুধু element stack এ push করার সময় current integer এর সাথে আপাতত stack এ থাকা element গুলোর মধ্যে mininum টি কে তুলনা করলেই হচ্ছে । ফলে প্রতি operation এবং প্রতি query এর জন্য আমাদের time complexity হচ্ছে O(1). আর total program এর memory complexity হচ্ছে O(n). 

LeetCode এর Min Stack problem টি same problem. 

(Problem Link : https://leetcode.com/problems/min-stack/ ).

আমরা নিজেরা উপরের idea ব্যবহার করে এই problem এর কোড লিখার চেষ্টা করব। আমি আমার solution কোডটি এখানে দিয়ে দিচ্ছি, কিন্তু আমরা সেটি দেখার আগে অবশ্যই নিজেরা চেষ্টা করব। 

#include<bits/stdc++.h> using namespace std; class MinStack { public:     /** initialize your data structure here. */     stack<pair<int,int> >stk;     int mn;     MinStack() {              }          void push(int x) {         if(!stk.empty())mn = min(stk.top().second,x);         else mn = x;         stk.push({x,mn});     }          void pop() {         stk.pop();     }          int top(){         return stk.top().first;     }          int getMin() {         return stk.top().second;     } }; /**  * Your MinStack object will be instantiated and called as such:  * MinStack* obj = new MinStack();  * obj->push(x);  * obj->pop();  * int param_3 = obj->top();  * int param_4 = obj->getMin();  */

Stack

Stack একটি linear data structure. ধরা যাক আমাদের কাছে কিছু plate আছে এবং এই plate গুলোকে আমরা একটির ওপর আরেকটি রেখে একটি স্তম্ভের মতো বানালাম । এখন স্তম্ভ বানানোর সময় আমরা যে plate টিকে সবার আগে নিয়েছিলাম সেটি সবার নিচে আছে, তাই না? হ্যাঁ । আবার যে plate টিকে ২য় বারে নিয়েছিলাম, সেটি নিচের দিক থেকে ২য় স্থানে আছে । এভাবে সর্বশেষ যে plate টি নিয়েছিলাম সেটি সবার উপরে আছে। এখন এই স্তম্ভের ওপর থেকে যদি আমরা একটি একটি করে plate সরিয়ে নেই, তবে সবার শেষে যেটি রেখেছিলাম সেটি আমরা সবার প্রথমে সরিয়ে নিবো, এরপর দ্বিতীয় সর্বশেষ যেটি রেখেছিলাম সেটি এবং এভাবে সবশেষে যেটি সবার প্রথমে রেখেছিলাম সেটি সরিয়ে নিবো । অর্থাৎ পুরো ব্যপারটি যা দাঁড়ালো সেটি হল - Last in, First out. আমরা যেটিকে শেষে রাখবো সেটিকে সবার আগে সরাবো। 

আমাদের stack data structure টি ঠিক একই ভাবে কাজ করে। Stack এ আমরা যে element সবার আগে push করব, pop বা তুলে নেওয়ার সময় ঠিক উপরের মত সেটি সবার পরে বের হবে। 

Stack data structure সম্পর্কিত সমস্যা সমাধানের জন্য আমরা STL এর stack ব্যবহার করব। এখানের যে function গুলা সবথেকে বেশি দরকার হয় সেগুলা হল push(), pop(), top(), size(), empty(). 

push() : push() ব্যবহার করে আমরা stack এর মধ্যে element রাখি। যেমন: আমরা যদি stack এ পর্যায়ক্রমে 10, 15, 3 এই তিনটি integer কে push করি, তবে সবার নিচে 10 এবং সবার উপরে 3 থাকবে যেটা অনেকটা নিচের ছবির মতো -

pop() : pop() ব্যবহার করে আমরা stack থেকে আপাতত সবার উপরে থাকা element কে তুলে নিতে পারি। যেমন উপরের stack এ আপাতত সবার উপরের element টি হল 3. এখন এই stack এর জন্য যদি আমরা pop() call করি, তবে এটি stack থেকে সবার উপরের element কে তুলে নিবে। ফলে stack এর মধ্যে আর দুইটি element অবশিষ্ট থাকবে। ব্যাপারটি আরও ভালো করে বুঝার জন্য আমরা নিচে ছবিটি লক্ষ করি। 

top() : top() ব্যবহার করে আমরা stack এ আপাতত সবার উপরে কোন element টি আছে সেটি জানতে পারব । যেমন আপাতত উপরে stack এ দুইটি element এর মধ্যে সবার উপরে আছে 15. তাই আমরা যদি top() call করি তবে return value হিসেবে আমরা 15 পাবো। এখানে একটি বিষয় লক্ষণীয় top() function টি শুধু সবার উপরের element কে নির্দেশ (indicate) করবে, pop() এর মত তুলে নিবে না, অর্থাৎ top() call করার পর stack এর কোন পরিবর্তন হবে না। 

size() : এই function আমাদের একটি integer value return করবে যেটি নির্দেশ করে আপাতত stack এ কতগুলো element আছে। যেমন আপাতত উপরের stack এ দুইটি element আছে, তাই এর size হবে 2.

empty() : যদি আমাদের stack এ কোন element না থাকে, তবে এই function টি true return করবে, অন্যথায় false return korbe. যেমন আপাতত উপরের stack এ দুইটি element আছে, তাই এর জন্য empty() call করলে return value হিসেবে আমরা false পাবো।

আমরা যদি উপরের ধাপ গুলোর coding implementation করি, তবে যেমন টা হবে :

#include<bits/stdc++.h> using namespace std; int main(){     stack<int>stk;     stk.push(10);     stk.push(15);     stk.push(3);     stk.pop();     int Top_element = stk.top();     int size_of_stack = stk.size();     bool b = stk.empty(); }

Big Integer এবং Java

অনেক ক্ষেত্রেই আমাদেরকে এমন কিছু বড় সংখ্যা নিয়ে কাজ করতে হয় যেগুলো integer কিংবা long long ডাটা টাইপের মধ্যে রাখা সম্ভব নয় । সে সকল ক্ষেত্রে C++ প্রোগ্রামাররা string ব্যবহার করে কাজটি করে থাকে । কিন্তু string ব্যবহার করে Big Integer implement করা code এর size অনেক বড় এবং কোড লিখা অনেক সময়সাপেক্ষ ব্যাপার । এক্ষেত্রে Java তে Big Integer এর জন্য built-in class আছে । Java তে Big Integer কিভাবে ব্যবহার করতে হয় তা শিখার জন্য কিছু ভাল উৎস :

ক)  https://www.tutorialspoint.com/java/math/java_math_biginteger.htm

খ)  https://www.geeksforgeeks.org/biginteger-class-in-java/

এ সম্পর্কিত নিচের problem টি দেখা যাক :

Codeforces Gym : 112 - ab-ba

Problem Link: https://codeforces.com/problemsets/acmsguru/problem/99999/112

এখানে বলা হয়েছে a ও b দুটি সংখ্যা দেওয়া আছে । আমাদেরকে ab-ba  এর মান print করতে হবে।

এখানে a ও b উভয়েরই মান ১০০ পর্যন্ত হতে পারে। ১০০১০০ কে তো আর integer কিংবা long long এ রাখা যাবে না। তাই এক্ষেত্রে আমাদেরকে BigInteger ব্যবহার করতে হবে। নিচে সমাধান দেওয়া হল: 

Codeforces Gym : 112 - ab-ba solution

import java.util.Scanner ; import java.math.BigInteger; public class Main{   public static void main(String[] args){     int a,b;     Scanner input = new Scanner(System.in);     a = input.nextInt();     b = input.nextInt();     BigInteger A = BigInteger.valueOf(a);     BigInteger B= BigInteger.valueOf(b);     System.out.printf("%d",A.pow(b).subtract(B.pow(a)));      } }

আরও কিছু Big integer সম্পর্কিত সমস্যা : Uva 10183 , URI 1279 , Project Euler Problem 13 , Project Euler Problem 15 , Project Euler Problem 16 

Prime Number Checking

 আমরা জানি ১ থেকে বড় যে সকল সংখ্যার ১ এবং ওই সংখ্যা ছাড়া অন্য কোনো উৎপাদক (divisor) নেই তাদেরকে মৌলিক সংখ্যা বলে । এক্ষেত্রে একটি বিষয় লক্ষণীয় যে ১ মৌলিক সংখ্যা নয়। 

এখন যদি বলা কোনো একটি সংখ্যা n মৌলিক কিনা যাচাই করার জন্য , তাহলে উপরের সংজ্ঞা অনুসারে আমরা যেটা করব যে ১ থেকে n সীমার মধ্যে ১ এবং n ছাড়া অন্য কোনো সংখ্যা দিয়ে n নিঃশেষে বিভাজ্য যায় কিনা । অর্থাৎ check করতে হবে যে  n % i == 0 কিনা, যেখানে 2<= i <=n-1. 

এখানে ২ থেকে n-1 কেন নিলাম? কারণ সব সংখ্যাই ১ এবং ওই সংখ্যা দ্বারা  নিঃশেষে বিভাজ্য যায়।

bool Check_if_Prime (int n) {

if(n<=1)return false;

for(int i=2; i<n; i++){

if(n % i == 0){

return false;

}

}

return true;

}

উপরের function টি যখন n এর জন্য call করা হবে , তখন function এর ভিতরের for loop টি ২ থেকে n-1 পর্যন্ত ঘুরবে এবং loop variable i এর প্রতিটি মানের জন্য n % i == 0 কিনা যাচাই করবে। যদি i এর কোনো মানের জন্য n % i == 0 হয়, এর মানে দাঁড়ায় ১ এবং n ছাড়াও n এর অন্য কোনো উৎপাদক আছে । তখন function টি false return করে এর কাজ সমাপ্ত করবে। অন্যথায় পুরো loop ঘুরেও যদি i এর কোন মানের জন্য n % i == 0 না হয় তবে true return করবে। তাহলে function টির time complexity দাঁড়ায় O(n-2) বা O(n) ( যেহেতু complexity হিসাব করার সময় constant value বাদ দেওয়া যায় ) । 

এখন আমরা function টির time complexity কমানোর চেষ্টা করি । প্রথমত খেয়াল করি , যদি ২ দ্বারা n নিঃশেষে বিভাজ্য না হয় তবে n অন্য কোন জোড় সংখ্যা দ্বারাই নিঃশেষে বিভাজ্য হবে না। তাহলে আমাদের function নিচের মতো হতে পারে :

bool Check_if_Prime (int n) {

if(n<=1)return false;

if(n % 2 == 0 && n>2){

return false;

}

for(int i=3; i<n; i+=2){

if(n % i == 0){

return false;

}

}

return true;

}

এক্ষেত্রে আমরা ২ ছাড়া অন্য কোন জোড় সংখ্যার জন্য n এর বিভাজ্যতা যাচাই করিনি । তাহলে আমাদের Check_if_Prime() function এর time complexity হল O(n/2) বা O(n) ( যেহেতু complexity হিসাব করার সময় constant value বাদ দিবো ) . অর্থাৎ কিছুটা optimization হলেও তাত্ত্বিক হিসাবে কোন পার্থক্য হয়নি । 

এখন খেয়াল করি একটি সংখ্যা n এর  উৎপাদক বা গুণনীয়ক যদি a হয় তবে (n/a) ও হবে n এর একটি গুণনীয়ক । 

ধরি b = n/a , যেখানে a হচ্ছে n এর একটি উৎপাদক । 

এখন , n = √n * √n

আবার, n = a * b

যদি a < √n হয় , তবে b কে অবশ্যই √n থেকে বড় হতে হবে ।

আবার যদি a < √n হয় , তবে b কে অবশ্যই √n থেকে ছোট হতে হবে ।

আর যদি a = √n হয় , তবে b অবশ্যই √n এর সমান হবে ।

তাহলে আমরা দেখতে পাচ্ছি যে (a,b) জোড়ায়  a  ও b এর মধ্যে যেকোনো একটি অবশ্যই √n এর সমান অথবা ছোট হবে । একটি উদাহরণ দিলে বিষয়টি আরও স্পষ্ট হবে । আমরা 24 এর উৎপাদকগুলোর দিকে তাকাই :

24 = 1 * 24

     = 2 * 12

     = 3 * 8

     = 4 * 6

আমরা দেখতে পাচ্ছি যে , 24 এর উৎপাদক জোড়াগুলোর মধ্যে সকল জোড়াতেই একটি উৎপাদক √24 এর চেয়ে ছোট বা সমান এই শর্ত মানে। 

তাহলে কোন সংখ্যা মৌলিক না হয়ে যৌগিক (composite) হলে এর অবশ্যই 2 থেকে √n সীমার মাঝে কোন না কোন উৎপাদক থাকবে।  সুতরাং , Check_if_Prime() function এর ভিতরের loop টি √n পর্যন্ত ঘুরালেই আমদের Prime Checking এর কাজটা হয়ে যাচ্ছে । 

bool Check_if_Prime (int n) {

if(n % 2 == 0 && n>2){

return false;

}

for(int i=3; i*i<=n; i+=2){

if(n % i == 0){

return false;

}

}

return true;

}

উপরের code snippet টি একটু খেয়াল করলেই আমরা দেখব যে , loop এর ভিতর আমরা condition হিসেবে   i <= sqrt(n)  ব্যবহার না করে i*i<=n করেছি । এর কারণ হচ্ছে sqrt(n) ব্যবহার করলে অনেক সময় double এর precision এ ঝামেলা করে। যেমন sqrt(9) এর জন্য 3 না এসে 2.9999…. আসতে পারে । তখন 2.9999…. কে integer এ রুপান্তর করলে সেটা 3 না হয়ে 2 হয়ে যাবে । তখন 9 কে মৌলিক সংখ্যা হিসেবে দেখাবে  । 

তাহলে এখন আমাদের Check_if_Prime() function এর time complexity দাঁড়ালো O(√n).এখন এই বিষয়ক একটি Online judge problem (URI 1165) দেখা যাক।

URI 1165 

Problem Link : ( https://www.urionlinejudge.com.br/judge/en/problems/view/1165 )

এই problem এ আমাদেরকে কিছু ইনপুট x এর জন্য , x prime number কিনা তা যাচাই করতে বলেছে। খুব সহজেই আমরা উপরে Check_if_Prime()  function টি ব্যবহার করে x prime কিনা তা বলে দিতে পারি। নিচে এর সমাধান দেওয়া হল :

URI 1165 Solution

#include <bits/stdc++.h> using namespace std; bool Check_if_Prime (int n) { if(n<=1)return false; if(n % 2 == 0 && n>2){ return false;             }             for(int i=3; i*i<=n; i+=2){ if(n % i == 0){                     return false;                         }             }             return true; } int main() {     int t;     cin>>t;     for(int i=0;i<t;i++){         int x;         cin>>x;         if(Check_if_Prime (x)){             cout<<x<<" eh primo\n";         }         else{             cout<<x<<" nao eh primo\n";         }     }     return 0; }

অনেক বড় কোন একটি সংখ্যা মৌলিক কিনা তা যাচাই করার জন্য আমরা JAVA তে BigInteger.isProbablePrime(int certainty) method টি ব্যবহার করতে পারি। এক্ষেত্রে পরীক্ষাধীন BigInteger টি যদি মৌলিক-সম্ভাব্য হয় তবে method টি true return করবে , আর যদি যৌগিক হয় তবে false rerturn করবে।

এই সম্পর্কিত একটি problem হল Codeforces 1033B - Square Difference . (Link : https://codeforces.com/contest/1033/problem/B) 

Codeforces 1033B - Square Difference

এই problem এ আমাদের কিছু test case দেওয়া থাকবে । প্রতিটি test case এ দুটি করে সংখ্যা a ও b দেওয়া থাকবে। আমাদের বলতে হবে (a2 - b2) মৌলিক কিনা । আমরা খুব সহজে JAVA তে  (a2 - b2) এর জন্য BigInteger.isProbablePrime(int certainty) method এর return value যাচাই করে বলে দিতে পারি (a2 - b2) মৌলিক কিনা । নিম্নে এর সমাধান দেওয়া হল :

Codeforces 1033B - Square Difference Solution

import java.util.*; import java.math.*; public class Main{     public static void main(String[] args){         int t;         Scanner src = new Scanner(System.in);         t = src.nextInt();         for(int i=0;i<t;i++){             BigInteger a,b;             a=src.nextBigInteger();             b=src.nextBigInteger();                         if((a.multiply(a).subtract(b.multiply(b))).isProbablePrime(10)){                 System.out.println("YES");             }             else{                 System.out.println("NO");             }         }     } }

উপরের এই problem টি আমরা চাইলে গণিত দিয়ে আরও সহজে করতে পারি। এখানে (a2 - b2) কে আমরা লিখতে পারি  (a+b) * (a-b) আকারে। এখন (a2 - b2) সংখ্যাটি মৌলিক হবে যদি ও কেবল যদি (a+b) ও (a-b) এর যেকোনো একটি মৌলিক হয় এবং অপরটি 1 হয়। যেহেতু a আর b কোনটিই 1 থেকে ছোট নয় , তাই (a+b) অবশ্যই 1 থেকে বড় হবে । অর্থাৎ (a2 - b2) সংখ্যাটিকে মৌলিক হতে হলে (a-b) কে অবশ্যই 1 হতে হবে এবং (a+b) কে অবশ্যই মৌলিক হতে হবে । তাহলে Check_if_Prime() funtion দিয়ে (a+b) মৌলিক কিনা এবং (a-b) যৌগিক কিনা এতটুকু যাচাই করাই যথেষ্ট হবে । নিচে সমাধান দেওয়া হল:

Codeforces 1033B - Square Difference Solution

#include<bits/stdc++.h> using namespace std; bool Check_if_Prime (unsigned long long n) {     if(n<=1ULL)return false;     if(n % 2ULL == 0 && n>2ULL){         return false;     }     for(unsigned long long i=3; i*i<=n; i+=2ULL){         if(n % i == 0){     return false;         }     }     return true; } int main(){     int t;     cin>>t;     for(int i=0;i<t;i++){          unsigned long long a ,b;          cin>>a>>b;          if(Check_if_Prime(a+b) && a-b==1){             cout<<"YES\n";          }          else{             cout<<"NO\n";          }     } }