Protected: Project Euler: 22


This content is password protected. To view it please enter your password below:

Advertisements

Big-Integer Tutorial with C


বড় বড় নাম্বার যোগ, গুন করার সময় আমরা প্রায়ই চিন্তায় পড়ে যাই। যেমন আমরা যদি C Data type range দেখি,

int (signed) –2,147,483,648 to 2,147,483,647
unsigned int 0 to 4,294,967,295
long long (signed) –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807
unsigned long long 0 to 18,446,744,073,709,551,615

অর্থ্যাৎ সবচেয়ে বেশি গেলেও ২০ ডিজিটের চেয়ে বড় নাম্বার রাখা না। কিন্তু আমাদের আরও বড় সংখ্যা নিয়ে কাজ করার প্রয়োজন হতে পারে। যেমন ধরা যাক, 100! বা 2^1000 যদি বের করতে চাই।

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

মনে করি, আমাদের দুইটা সংখ্যা দেয়া আছে, 87654 and 74692
এই দুইটা সংখ্যা যোগ করতে হবে।


8
7
6
5
4

7
4
6
9
2

প্রথমে আমরা দুইটা সংখ্যা নিচে নিচে লিখে ফেললাম, এবার আমরা যোগ শুরু করব।


8
7
6
5
4

7
4
6
9
2





6

৪ যোগ ২ সমান ৬


8
7
6
5
4

7
4
6
9
2




4
6

৫ যোগ ৯ সমান ১৪
১৪-এর ৪ বসালাম, হাতে থাকল ১


8
7
6
5
4

7
4
6
9
2



3
4
6

৬ যোগ ৬ সমান ১২
হাতের ১ যোগ করে পেলাম ১৩
৩ বসালাম, হাতে থাকল ১

….
বুঝাই যাচ্ছে আমি কি করতে যাচ্ছি। সবশেষে পুরো বিষয়টা দাড়াবে এরকম

8

7

6

5

4

7

4

6

9

2

1

6

2

3

4

6

এই কাজটাই এখন আমরা প্রোগ্রাম দিয়ে করব। মানে কম্পিউটারকে দিয়ে করাব।

প্রথমে সংখ্যাগুলাকে ডিজিটে ভাগ করে Array-তে নিব।


#include <cstdio>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    return 0;
}

একটা ছোট সমস্যা। আমরা তো যোগ করা শুরু করি ডানদিক থেকে। কিন্তু আমাদের অ্যারে শুরু হয় বামদিক থেকে।
মানে হল, আমাদের প্রথমে যোগ করতে হবে ৪ এবং ২; কিন্তু এগুলা অ্যারেতে শেষ এলিমেন্ট। কি করা যেতে পারে?

আমরা Array উল্টাদিক থেকে পড়া শুরু করতে পারি অথবা অ্যারেটাকেই উল্টে নিতে পারি।
আমরা বরং অ্যারেটাকে উল্টে নিই। তাতে করে আমাদের অ্যারে দেখাবে এরকম।

4
5
6
7
8

2
9
6
4
7

এবং যোগ করার পর আমাদের যোগফল অ্যারেটা হবে এরকম

4
5
6
7
8

2
9
6
4
7

6
4
3
2
6
1

সমস্যা নাই যদিও। সবকাজ শেষ হবার পর আমরা রেজাল্ট অ্যারেটা উল্টে নিব। তাতেই সবকিছু সোজা হয়ে যাবে।

#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    return 0;
}

এবার যোগ করা শুরু করি।

প্রথমে যখন আমরা যোগ করা করি তখন কিন্তু আমাদের হাতে কিছু থাকে না।
আমরা একটা variable নিবো carry;
আমাদের হাতে যা থাকে সেটা এই carry তে থাকবে। প্রথমে হাতে কিছুই থাকে না, তাই carry = 0

এরপর আমরা যোগ করব, firstNumber [i] + secondNumber [i] + carry এইভাবে

যোগফলটা carry-তেই রাখলাম।

#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
    }
    
    return 0;
}

কিভাবে কাজটা হবে সেটা একটু বুঝার চেষ্টা করি।
আমারা প্রথম দুইটা ডিজিটের যোগফল বের করালাম। এবং সেই যোগফল carry-তে আছে।
এখন দেখতে হবে, carry >= 10 কিনা।

যদি carry >= 10 হয় তাহলে আমরা রেজাল্টে বসাব, carry % 10
এবং আমাদের হাতে থাকবে carry / 10

যদি carry < 10 হয় তাহলে আমরা রেজাল্টে বসাব, carry
এবং আমাদের হাতে থাকবে 0

এই দুইটা if-else কন্ডিশন আসলে একই কাজ করে। মানে একটা লাইন দিয়েই দুইটা কাজ করা যায়; if-else লাগবে না।
যেমন ধরি, আমাদের একটা নাম্বার আছে, number
এবং আমরা রেজাল্টে বসাব, number % 10
এবং carry তে বসাব number / 10

result = number % 10
carry = number / 10

একটু খেয়াল করলে দেখা যায়, number value 10 থেকে বড় বা ছোট যাই হোক না কেন, result and carry value সবসময় একই আসবে। একটু চিন্তা করে দেখেন


    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }

এইভাবে লুপটা ঘুরতে থাকবে। এবং লুপ ঘুরা শেষ হলে আমরা আমাদের উত্তরটা পেয়ে যাব result অ্যারেতে।

একটা সমস্যা কিন্তু থেকে গেল। এখন যদি আমরা result array print দিই তাহলে কি পাব?

64326

result অ্যারেটা reverse করতে হবে, সেটা আমরা জানি। কিন্তু 1 টা কোথায় গেল?

খেয়াল করে দেখেন, লুপ শেষ হয়ে গেলেও আমাদের carry-তে একটা 1 ছিল, যেটা আমরা result array তে ঢুকাতে পারি নাই। সেটা ঢুকাতে হবে।

এইক্ষেত্রে আমরা জানি, carry তে এখন 1 আছে। কিন্তু ধরেন, আমরা অনেক অনেক বড় নাম্বার যোগ করছি। তখন হয়তো carry-তে 54362; এতবড় একটা নাম্বারও থাকতে পারে। তাই না?

এইজন্য আমরা একটা লুপ চালাবো। এবং একটা একটা করে ডিজিট carry থেকে নিয়ে result array তে ঢুকাব।


    int carry = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [i] = carry % 10;
        carry /= 10;
    }
    
    while ( carry ) {
        result [i] = carry % 10;
        carry /= 10;
        i++;
    }
    
    return 0;

আরেকটা সমস্যা। সেটা হল, for loop এর loop variable i-কে আমরা while loop-এর ভেতরে পাব না।

কিন্তু while loop-এর ভেতরে আমাকে তো জানতে হবে, result array-তে কত নাম্বার index থেকে আমি ঢুকানো শুরু করব?

for loop-এ যে পর্যন্ত ঢুকানো হয়েছিল, তারপরের থেকে, তাই না?

বেশি ঝামেলা না করে আমরা result array-টার জন্য আলাদা একটা variable রাখতে পারি।

সবশেষে আমরা result array টা reverse করে দিব।


#include <cstdio>
#include <algorithm>

using namespace std;

int main (int argc, char *argv [])
{
    int firstNumber [] = {8, 7, 6, 5, 4};
    int secondNumber [] = {7, 4, 6, 9, 2};
    int result [100];

    reverse(firstNumber, firstNumber + 5);
    reverse(secondNumber, secondNumber + 5);
    
    int carry = 0;
    int resultLength = 0;
    
    for ( int i = 0; i < 5; i++ ) {
        carry = firstNumber [i] + secondNumber [i] + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }
    
    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }
    
    reverse(result, result + resultLength);
    
    return 0;
}

এখন কথা হল, আমরা এইখানে firstNumber and secondNumber initialize করে দিয়েছিলাম। এটা তো আসলে করা যাবে না। আমাদেরকে ইনপুট নিতে হবে। কিন্তু অনেক বড় বড় সংখ্যা আমরা কিভাবে ইনপুট নিব?

ইনপুটটা আমরা string হিসেবে নিতে পারি।
যদি তাই করি, তাহলে যোগ করার সময় আমাদের একটা কাজ অতিরিক্ত করতে হবে।

সেটা হল, এইক্ষেত্রে ডিজিটগুলা তো আসলে একেকটা character; তাই যোগ করার সময় character গুলাকে ডিজিট করে নিতে হবে।

মানে হল, ‘0’-কে convert করে 0 করবো
‘1’-কে convert করে 1 করবো

আমরা কোডটা দেখে ব্যাপারটা বুঝার চেষ্টা করি।


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    char secondNumber [N];
    int result [N + 10];

    scanf ("%s %s", firstNumber, secondNumber);

    reverse(firstNumber, firstNumber + strlen(firstNumber));
    reverse(secondNumber, secondNumber + strlen(secondNumber));

    int carry = 0;
    int resultLength = 0;

    for ( unsigned int i = 0; i < strlen(firstNumber); i++ ) {
        carry = (firstNumber [i] - '0') + (secondNumber [i] - '0') + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

অতীব চমকপ্রদ একটা কোড করে ফেললাম। এবার একটা ইনপুট দিয়ে টেস্ট করা যাক।

input:
123
1

expected output:
124

actual output:
🙄

ঘটনা যেটা হইছে সেটা অনেকটা এমন

1
2
3
আলু
পটল
1
😕
😐
4

মানে হল, ২য় নাম্বারটা ছোট হবার কারনে তার আগের ঘরগুলাতে Garbage value থাকবে।

সমাধান যেটা করা যেতে পারে, যোগ শুরু করার আগেই অ্যারেগুলা 0 দিয়ে initialize করে দেয়া, যাতে করে আলু, পটল থাকতে না পারে।

0 দিয়ে initialize করে দেয়ার পর আমরা ইনপুট নিবো। ইনপুটের নাম্বারগুলো 0 কে replace করে বসে যাবে। আমাদের অ্যারে সাইজ তো বেশ বড়, ইনপুট নেয়ার পর যে ঘরগুলো খালি থাকবে সেগুলোতো তখন 0 পাওয়া যাবে, আলু পটল না।

আরেকটা ছোট সমস্যা আছে।
আমরা তো এখন string হিসেবে ইনপুট নিচ্ছি। আমরা জানি, string ইনপুট নিলে শেষে একটা

 End of string ('\0') character 

automatically বসে যায়। কাজেই কাজ শুরুর আগে এটাকেও 0 করে দিতে হবে।

এরপরের চিন্তার বিষয় হল, আমরা আমাদের লুপটা কতবার চালাব?

উত্তর হল, দুইটা নাম্বারের মধ্যে যে নাম্বারের length সবচেয়ে বেশি ততবার চালাব।

আমি কি ঠিক বলতেছি? আচ্ছা, এবার তাহলে কোডটা দেখা যাক।


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    char secondNumber [N];
    int result [N + 10];

    // initialize the array with '0'
    memset(firstNumber, '0', sizeof firstNumber);
    memset(secondNumber, '0', sizeof secondNumber);

    scanf ("%s %s", firstNumber, secondNumber);

    int firstNumberLength = strlen (firstNumber);
    int secondNumberLength = strlen (secondNumber);
    int maximumLength = max (firstNumberLength, secondNumberLength);

    reverse(firstNumber, firstNumber + strlen(firstNumber));
    reverse(secondNumber, secondNumber + strlen(secondNumber));

    // normalize the last end of string character
    firstNumber [firstNumberLength] = '0';
    secondNumber [secondNumberLength] = '0';

    int carry = 0;
    int resultLength = 0;

    for ( int i = 0; i < maximumLength; i++ ) {
        carry = (firstNumber [i] - '0') + (secondNumber [i] - '0') + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

যোগের কাহিনি শেষ। :mrgreen:

এবার আসি গুনের কাহিনিতে। ধরি, আমাদের গুন করতে দেয়া হল,
9452 X 675

সাধারনত আমরা ছোটবেলায় গুনটা যেভাবে করতাম,




9
4
5
2



X
6
7
5


4
7
2
6
0

6
6
1
6
4
X
5
6
7
1
2
X
X
6
3
8
0
1
0
0

এইবার আমরা বড়বেলার গুনফল বের করব। এবং সেটা দেখতে হবে অনেকটা এমন




9
4
5
2





X
675
6
3
8
0
1
0
0

মানে একবারেই আমরা গুনফলটা বের করে ফেলব। ঘটনাটা আমি বুঝানোর চেষ্টা করি।

এখানে 675 কে অ্যারেতে আলাদা আলাদা ডিজিট হিসেবে চিন্তা না করে একটা সংখ্যা হিসেবে চিন্তা করতে হবে। এবং একবারে 675 দিয়েই গুনের কাজ করতে হবে। যেমন:

675 X 2    =    1350 
675 X 50   =   33750
675 X 400  =  270000
675 x 9000 = 6075000
-----------------------
             6380100

অথবা আরেকটা কাজ করা যায়। মনে করি আমাদের কাছে একটা খালি অ্যারে আছে








675 x 2 = 1350
put the last 0 in the array
carry = 135







0

675 X 5 = 3375 + carry = 3375 + 135 = 3510
put the last 0 in the array
carry = 351






0
0

675 X 4 = 2700 + carry = 2700 + 351 = 3051
put the last 1 in the array
carry = 305





1
0
0

675 X 9 = 6075 + carry = 6075 + 305 = 6380
put the last 0 in the array
carry = 638




0
1
0
0

এখন হাতে যে carry আছে সেটাই অ্যারেটার আগে বসিয়ে দিতে হবে

6
3
8
0
1
0
0

এবার দেখব আমাদের সবশেষ কোড


#include <cstdio>
#include <algorithm>
#include <cstring>

#define N 100

using namespace std;

int main (int argc, char *argv [])
{
    char firstNumber [N];
    int secondNumber;
    int result [N + 10];

    scanf ("%s %d", firstNumber, &secondNumber);

    int firstNumberLength = strlen (firstNumber);

    reverse(firstNumber, firstNumber + strlen(firstNumber));

    int carry = 0;
    int resultLength = 0;

    for ( int i = 0; i < firstNumberLength; i++ ) {
        carry = ((firstNumber [i] - '0') * secondNumber) + carry;
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    while ( carry ) {
        result [resultLength++] = carry % 10;
        carry /= 10;
    }

    reverse(result, result + resultLength);

    for ( int i = 0; i < resultLength; i++ )
        printf ("%d", result [i]);

    printf ("\n");

    return 0;
}

একটাই প্রশ্ন থেকে যায়, ২য় নাম্বারটা আমরা কেন অ্যারেতে নিলাম না? যদি ২য় নাম্বারটা অনেক অনেক বড় হয় তখন কি হবে?

উত্তর: হবে আর কি কিছু একটা। এই শিশু বয়সে ওইসব নিয়ে টেনশন করার কি দরকার? চেপে যান 😐

UIU: Project Euler Guideline


প্রজেক্ট অয়লারের প্রথম ২৫ টা প্রবলেম সবারই সলভ করা উচিত। ৫০ টা হলে বেশ ভাল, ৭৫ টা হলে অতি ভাল, আর ১০০+ হলে সিরাম

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

আমি জানি, প্রথম সেমেস্টার শেষ করা একজন স্টুডেন্ট যতটুকু জানে, সেই হিসেবে কাজটা কঠিন বটে
কিন্তু তারপরও আমি বলব আপনি নিজে নিজে চেষ্টা করেন, সাহায্য ছাড়া শেখার চেষ্টা করতে থাকেন
তাতে করে যদি আপনার একটা প্রবলেম সলভ করতে ১ সপ্তাহও লাগে, সেটাও অনেক ভালো হবে
অনেক চিন্তা এবং চেষ্টার পরেও যদি কোন কিছু বুঝতে না পারেন তখন এই পোস্টটা দেখবেন

এই পোস্টে আমি কোনো কোড করি নাই .. সল্যুশন করার কোনো পদ্ধতি বলা হয় নাই
শুধু প্রবলেমটায় কি করতে হবে সেটা বলা আছে .. আর হয়ত কিছু ছোট হিন্টস পাবেন
এর থেকে বেশি হেল্প আসলে দরকার নাই, এর পরের কাজটুকু আপনি করবেন, যতই সময় লাগুক

প্রতিটা প্রবলেমের জন্য একটা আলাদা করে পোস্ট দেয়া আছে .. সেখানে প্রবলেমটার কোড করে দেয়া আছে
ট্রিকস নিয়ে আলোচনা করা আছে, এবং আরো অন্যভাবে প্রবলেমটা সলভ করা যায় কিনা সেটা বলা আছে
আমি ছাড়াও সেখানে আপনাদের বড় ভাই/আপুদের কমেন্ট, সাজেশন পাবেন, তারা কিভাবে সলভ করেছে
তবে সেই পোস্টগুলা পাসওয়ার্ড প্রোটেক্টেড, পোস্টে ঢুকার জন্য ওই প্রবলেমের উত্তরটাই পাসওয়ার্ড 😀
কাজেই প্রবলেমটা নিজে সলভ করার আগে আপনি পোস্টে ঢুকতে পারবেন না .. এটা একরকম কৌশল
তবে অবশ্যই এতে ফাঁক আছে .. যেমন বন্ধুর কাছ থেকে উত্তর জেনে পোস্টে ঢুকে যেতে পারেন
এই ব্যপারে আমরা কিছু বলব না .. এটা সম্পূর্ণই আপনার ব্যক্তিগত বিবেচনার উপর নির্ভর করে
আপনি এখন যথেষ্টই বড়, প্রতিটা জিনিস আপনাকে বলে দিতে হবে এমনটা নিশ্চয়ই আশা করেন না 🙂

প্রবলেম খুজতে স্ক্রল করে নিচে যেতে হবে না
url-এর পরে একটা হ্যাশ (#) এবং তারপর প্রবলেম নাম্বার লিখে Enter দেন
যেমন: https://tausiq.wordpress.com/2013/06/10/uiu-project-euler-guideline/#2

Problem 1

3 বা 5-এর যতগুলা গুণীতক আছে, যারা 1000 থেকে ছোট তাদের যোগফল বের করতে হবে।
গুণীতক মানে বুঝেন তো? ওই গুণীতক আর কি
যেমন, 9 এর গুণীতক হল: 9, 18, 27, 36, 45, 54 .. এইগুলা
9-এর গুণীতকগুলা অবশ্যই 3 এর গুণীতক। কারন, 9 নিজে হল 3 এর গুণীতক
9 হল 3 এর গুণীতক কারন, 9 কে 3 দিয়ে নিঃশেষে ভাগ করা যায়।

Problem 2

১ম ফিবোনাচ্চি নাম্বার ধরে নিলাম, 1
২য় ফিবোনাচ্চি নাম্বার ধরে নিলাম, 2
তাহলে ৩য় ফিবোনাচ্চি নাম্বার হবে = ১ম ফিবোনাচ্চি নাম্বার + ২য় ফিবোনাচ্চি নাম্বার
বা, ৩য় ফিবোনাচ্চি নাম্বার হবে = 1 + 2 = 3
৪র্থ ফিবোনাচ্চি নাম্বার হবে = ২য় ফিবোনাচ্চি নাম্বার + ৩য় ফিবোনাচ্চি নাম্বার
বা, ৪র্থ ফিবোনাচ্চি নাম্বার হবে = 2 + 3 = 5
এইভাবে…

.. terms in the Fibonacci sequence whose values do not exceed four million ..

মানে হল, এমন ফিবোনাচ্চি নাম্বারগুলা নিতে হবে যাদের ভ্যালু ৪০ লক্ষ থেকে বেশি না।

find the sum of the even-valued terms

এবং ওই নাম্বারগুলা থেকে শুধুমাত্র জোড়গুলা নিতে হবে। এই জোড়গুলার যোগফল আউটপুট।

এই প্রবলেমটা সলভ করতে আমাদের যে ফিবোনাচ্চি নাম্বারগুলা লাগবে সেগুলা হল
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
.
.
.
3524578
5702887
4613732

Problem 3

প্রাইম মানে প্রাইম
আর ফ্যাক্টর মানে ফ্যাক্টর, মানে, গুণনীয়ক বা উৎপাদক।
যে সংখ্যাগুলা দিয়ে 96 কে নিঃশেষে ভাগ করা যায়, সেগুলা হল 96-এর উৎপাদক।
যেমন: 1, 2, 3, 4, 6, 8, 12, 16 24, 32, 48, 96
প্রাইম ফ্যাক্টর হল, এমন ফ্যাক্টর যেগুলা প্রাইম
যেমন: 5, 7, 13, 29 হল প্রাইম এবং এগুলা 13195 এর ফ্যাক্টর। কাজেই, 5, 7, 13, 29 হল 13195-এর প্রাইম ফ্যাক্টর।
600851475143 সবচেয়ে বড় প্রাইম ফ্যাক্টরটাই আউটপুট

Problem 4

প্যালিনড্রোম হল, যাকে উল্টা করলেও কাহিনি একই থাকে। মানে, উল্টা করলেও যা, সোজা থাকলেও তাই। যেমন: “MADAM”, এই শব্দটা উল্টা করলেও একই থাকে। ইংরেজিতে বিখ্যাত কিছু প্যালিনড্রোম আছে। যেমন; “Never odd or even”। স্পেসগুলা বাদ দিলে এটা একটা প্যালিনড্রোম। একইভাবে, নাম্বারও প্যালিনড্রোম হয়। যেমন: 23432, 654456 ইত্যাদি।

সংখ্যা এবং অঙ্ক এই দুইটা জিনিসের পার্থক্য বুঝতে হবে। যেমন:
১৯ = একটা সংখ্যা।
১৯ = দুই অংকের একটা সংখ্যা
একইভাবে, ৯ একটা সংখ্যা, আবার ৯ একটা অংকও হতে পারে। এটা আমরা সবাই বুঝি, Number and Digit

দুই অংকের সবচেয়ে ছোট সংখ্যা ১০ এবং দুই অংকের সবচেয়ে বড় সংখ্যা ৯৯
দুই অংকের যেকোন দুইটা সংখ্যার গুনফল, সর্বনিম্ন তিন অংকের একটা সংখ্যা হতে পারে এবং সর্বোচ্চ চার অংকের একটা সংখ্যা হতে পারে।

মজার ব্যপার হল, এই গুনফলটা প্যালিনড্রোম হতে পারে। যেমন ধরেন, ১১ x ১১ = ১২১, একটা প্যালিনড্রোম।
তো ঘটনা হইল,
১. আমরা দুই অংকের যেকোন দুইটা সংখ্যার যতগুলা গুনফল হতে পারে সব বের করলাম।
২. গুনফলগুলার মধ্যে যতগুলা প্যালিনড্রোম আছে সেগুলা আলাদা করলাম।
৩. এই আলাদা করা সংখ্যাগুলার মধ্যে সবচেয়ে বড় সংখ্যাটা হল ৯০০৯
৪. একইভাবে কাজটা তিন অংকের দুইটা সংখ্যার জন্য করতে হবে। এবং সবেচেয়ে বড় প্যালিনড্রোমটা আউটপুট দিতে হবে।

ওহ খোদা! আমি প্যাচাইতেও পারি অনেক। দুই লাইনের একটা ছোট প্রবলেমের কয় লাইন বণর্না লিখলাম!!

Problem 5

৪ এবং ১০ দুইটা সংখ্যা নিয়ে উদাহরন দিই। ৪ * ১০ = ৪০
৪০ কে ৪ দিয়ে এবং ১০ দিয়ে নিঃশেষে ভাগ করা যায়।
কিন্তু দেখেন, ২০ কেও ৪ দিয়ে এবং ১০ দিয়ে নিঃশেষে ভাগ করা যায়। এবং ২০ হল ৪০ থেকে ছোট।
কিন্তু ২০ থেকে ছোট এমন কোন সংখ্যা পাওয়া যাবে না, যেটাকে ৪ এবং ১০ দিয়ে ভাগ করা যায়।
একইভাবে, ২৫২০ হল সবচেয়ে ছোট সংখ্যা যেটাকে ১ থেকে শুরু করে ১০ পর্যন্ত সবগুলা সংখ্যা দিয়ে ভাগ করা যায়।
সবচেয়ে ছোট সংখ্যা বের করতে হবে যেটাকে ১ থেকে শুরু করে ২০ পর্যন্ত সবগুলা সংখ্যা দিয়ে ভাগ করা যায়।

Problem 6

খুবই বাংলা প্রবলেম .. একটা উদাহরণ দেয়া আছে ১০ পর্যন্ত
একই কাজ ১০০ পর্যন্ত করে আউটপুট দিতে হবে
ভুল করে কোনো মিসটেক না করলেই হয়ে যাবে

Problem 7

দশ হাজার একতম প্রাইম আউটপুট দিতে হবে
প্রথম থেকে শুরু করে সামনে যেতে থাকেন যতক্ষণ ১০০০১-তম প্রাইম না পাওয়া যায়

Problem 8

একটা নাম্বার দেয়া আছে
সেই নাম্বারে অঙ্ক আছে ১০০০টা
মানে ১০০০ ডিজিটের একটা নাম্বার দেয়া আছে

এই নাম্বারের যেকোনো ৫টা পাশাপাশি ডিজিটের সবচেয়ে বড় গুনফল আউটপুট দিতে হবে

এখন কথা হলো, ইনপুট নিবেন কিভাবে?

পুরো নাম্বার কপি করে একটা ফাইলে পেস্ট করেন, তারপর ফাইল থেকে ইনপুট নেন
বা,
এইভাবেও কোডের ভিতরে কপি-পেস্ট করে নিতে পারেন

char input [5] [50 + 5] =
{{"73167176531330624919225119674426574742355349194934"},
{"96983520312774506326239578318016984801869478851843"},
{"85861560789112949495459501737958331952853208805511"},
{"12540698747158523863050715693290963295227443043557"}};

আমাদের ইনপুট নেয়া শেষ হলো; তারপরের কাজ হলো ৫টা ডিজিট বের করা
যেকোনো ৫টা পাশাপাশি ডিজিট আসলে এলোমেলোভাবে নিলে হবে না
আমাদের প্রথম থেকে শুরু করে সবগুলা পাশাপাশি ৫টা ডিজিটের গুনফল বের করতে হবে

যেমন,
এই নাম্বারের প্রথম ৫ টা ডিজিটের গুনফল কত?

7 * 3 * 1 * 6 * 7 = 882

তারপরের ৫টা ডিজিটের গুনফল কত?

1 * 7 * 6 * 5 * 3 = 630

উহু, হলো না

তারপরের ৫টা ডিজিটের গুনফল হবে আসলে

3 * 1 * 6 * 7 * 1 = 126

শুধুমাত্র প্রথম ডিজিটটা বাদ, তারপর থেকে ৫টা ডিজিট নিতে হবে
কারণ বলা আছে, যেকোনো ৫টা পাশাপাশি ডিজিট
31671 কিন্তু ৫টা পাশাপাশি ডিজিট

Problem 9

a, b, c তিনটা নাম্বারের গুনফল বের করতে হবে
যেন, a + b + c = 1000 হয়
এবং a * a + b * b = c * c হয়

Problem 10

২০ লক্ষের নিচে যত প্রাইম নাম্বার আছে তাদের যোগফল বের করতে হবে

N.B: UIU: Prime Number using Square_Root Algorithm

Problem 11

একটা গ্রীড দেয়া আছে, এটাকে ম্যাট্রিক্সও বলা যায়। এই গ্রীড থেকে পাশাপাশি যেকোন ৪ টা সংখ্যা নিতে হবে।
পাশাপাশি সংখ্যাগুলা উপর, নিচ, ডান, বাম বা কোনাকুনি হতে পারে। যেকোন ৪ টা সংখ্যা নেবার পর সবচেয়ে বড় গুনফলটাই আউটপুট।
ট্রিকস হল, কোনাকুনি কিন্তু দুই ধরনের হয় ডান এবং বাম। মানে, Left Diagonal and Right Diagonal .. like, X

Problem 12

Triangle Number খুব সহজ।

1st triangle number: 1
2nd triangle number: 1 + 2 = 3
3rd triangle number: 1 + 2 + 3 = 6
4th triangle number: 1 + 2 + 3 + 4 = 10
5th triangle number: 1 + 2 + 3 + 4 + 5 = 15

প্রথম কয়েকটা Triangle number এর গুনণীয়ক দেয়া আছে।
সেখান থেকে দেখা যায়, ২৮ হল প্রথম Triangle number যার গুননীয়ক ৫ টার বেশি
এখন, প্রথম Triangle number খুজে বের করতে হবে যার গুননীয়ক ৫০০ টার বেশি
একটা মজার ব্যপার হল, যদি বলা হয়, ৫টার বেশি গুননীয়ক আছে, তার মানে কিন্তু ৬টা গুনণীয়ক আছে এমনটা বলা যাবে না। আরও বেশি থাকতে পারে।

Problem 13

এইখানে ১০০টা সংখ্যা দেয়া আছে, এবং প্রতিটা সংখ্যা ৫০ ডিজিটের।
এই সংখ্যাগুলা যোগ করতে হবে; তারপর যোগফলের প্রথম ১০টা ডিজিট আউটপুট।
একেবারে বাংলা পদ্ধতিতে যোগ করতে হবে।
ধরেন, ৬৯৫৪৭৬ এবং ৮২৫৪৮৬ সংখ্যা দুইটা আমরা যোগ করতে চাই।
প্রথমে সংখ্যা দুইটাকে অ্যারেতে নিতে হবে। অ্যারেতে প্রতিটা এলিমেন্ট হবে একটা করে ডিজিট
তারপরে ছোটবেলায় আমরা যেভাবে যোগ করেছিলাম, ৬ + ৬ = ১২; ২ লিখলাম; হাতে থাকল ১; সেইভাবে করতে হবে

		6	9	5	4	7	6
		8	2	5	4	8	6
	1	5	2	0	9	6	2

N.B: Big-Integer Tutorial with C

Problem 14

একটা নাম্বার জোড় হলে সেটাকে ২ দিয়ে ভাগ করবেন। বেজোড় হলে ৩ দিয়ে গুন করে ১ যোগ।
নতুন যে নাম্বারটা আসবে সেটা জোড় হলে ২ দিয়ে ভাগ করবেন। বেজোড় হলে ..
এই কাহিনি করতে থাকলে একসময় আপনি ১ পাবেন।

এইভাবে ১৩ থেকে শুরু করে ১ পেতে গেলে আমরা ১০টা সংখ্যার একটা চেইন পাই।
এমন একটা নাম্বার খুজতে হবে যেটা দশ লক্ষ থেকে ছোট এবং সবচেয়ে বড় চেইন তৈরী করে।

এমন হতে পারে, একটা নাম্বার পেলেন যেটা দশ লক্ষ থেকে ছোট এবং সবচেয়ে বড় চেইন তৈরী করে। কিন্তু সেই চেইনের কোন একটা নাম্বার ১০ লক্ষ থেকে বড় তাহলে সেটা উত্তর হবে না।

Problem 15

ও খোদা!! এইটা কি??

Problem 16

প্রবলেম ১৩-এর মতই, বাংলা পদ্ধতিতে গুন করতে হবে। গুন করে প্রথমে 2^1000 বের করতে হবে। তারপর তো বুঝেনই

N.B: Big-Integer Tutorial with C

Problem 17

বেশ মজার প্রবলেম। এইখানে একটা প্যাটার্ন আছে, সেটা খুজে বের করতে হবে।
যেমন:
one
two
three
four
….

thirty one
thirty two
thirty three
….

ninety one
ninety two
ninety three
….

one hundred and thirty one
one hundred and thirty two
one hundred and thirty three
….

nine hundred and ninety one
nine hundred and ninety two
nine hundred and ninety three

Problem 18

ওয়াও! কত সুন্দর একটা পিরামিড 😀

Problem 19

পহেলা জানুয়ারী ১৯০১ হইতে ৩১ ডিসেম্বর ২০০০ পর্যন্ত কতগুলা মাসের প্রথমদিন রবিবার ছিল? (কস কি মমিন!! :O)

Problem 20

প্রবলেম ১৬-এর মতই

Problem 21

Proper divisor of A

মানে হল, যে সংখ্যাগুলো A থেকে ছোট এবং যেগুলো দিয়ে A-কে ভাগ করা যায়।
যেমন: 220-এর Proper divisor: 1, 2, 4, 5, 10, 11, 20, 22, 44, 55

A-এর Proper divisor গুলার যোগফল হল d(A)
যেমন: d(220) = 1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 = 284

মজার ব্যপার হল, d(220) = d(284)
এই মজার ব্যপারটা যে নাম্বারগুলোর ক্ষেত্রে ঘটে সেগুলা Amicable number

10000-এর নিচে সবগুলা Amicable নাম্বারের যোগফল বের করতে হবে। কিছু Amicable number দেখা যাক।

220 284
... ...
2620 2924
... ...
6232 6368

Problem 22

কস কি মমিন!!
একটা বলে ফাইল আছে, তার মধ্যে নাকি ৫ হাজার নাম আছে!
নামগুলা সর্ট করতে হবে।

তারপর প্রতিটা নামের একটা করে মান (value) থাকবে। সবগুলা নামের ভ্যালুর যোগফলই উত্তর।

নামের ভ্যালু বের করা সহজ।
প্রতিটা নামের অ্যালফাবেটিক মান বের করবেন; তারপর নামের পজিশনের সাথে গুন করবেন।

Problem 23

একটা সংখ্যার গুনণীয়কগুলার যোগফল যদি সেই সংখ্যাটাই হয় তবে তাকে পারফেক্ট নাম্বার বলে।
যেমন: 28
1 + 2 + 4 + 7 + 14 = 28

একটা সংখ্যার গুনণীয়কগুলার যোগফল যদি সেই সংখ্যার চেয়ে বড় হয় তবে তাকে abundant number বলে।
যেমন: 12
1 + 2 + 3 + 4 + 6 = 16

একটা সংখ্যার গুনণীয়কগুলার যোগফল যদি সেই সংখ্যার চেয়ে ছোট হয় তবে তাকে deficient number বলে।

24 হল সবচেয়ে ছোট সংখ্যা যেটাকে দুইটা abundant number-এর যোগফল হিসেবে লেখা যায়।
28123 থেকে বড় সবগুলা সংখ্যাকেই নাকি দুইটা abundant number-এর যোগফল হিসেবে লেখা যায়।

যেসব সংখ্যাকে দুইটা abundant number-এর যোগফল হিসেবে লেখা যায় না তাদের যোগফল আউটপুট।

প্রথম কয়টা abundant number দেখেন, ভাল লাগবে। 🙂

1 + 2 + 3 + 4 + 6 = 16 (12)
1 + 2 + 3 + 6 + 9 = 21 (18)
1 + 2 + 4 + 5 + 10 = 22 (20)
1 + 2 + 3 + 4 + 6 + 8 + 12 = 36 (24)
1 + 2 + 3 + 5 + 6 + 10 + 15 = 42 (30)
1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 = 55 (36)
1 + 2 + 4 + 5 + 8 + 10 + 20 = 50 (40)
1 + 2 + 3 + 6 + 7 + 14 + 21 = 54 (42)
1 + 2 + 3 + 4 + 6 + 8 + 12 + 16 + 24 = 76 (48)
1 + 2 + 3 + 6 + 9 + 18 + 27 = 66 (54)
1 + 2 + 4 + 7 + 8 + 14 + 28 = 64 (56)
1 + 2 + 3 + 4 + 5 + 6 + 10 + 12 + 15 + 20 + 30 = 108 (60)
1 + 2 + 3 + 6 + 11 + 22 + 33 = 78 (66)
1 + 2 + 5 + 7 + 10 + 14 + 35 = 74 (70)
1 + 2 + 3 + 4 + 6 + 8 + 9 + 12 + 18 + 24 + 36 = 123 (72)
1 + 2 + 3 + 6 + 13 + 26 + 39 = 90 (78)
1 + 2 + 4 + 5 + 8 + 10 + 16 + 20 + 40 = 106 (80)
1 + 2 + 3 + 4 + 6 + 7 + 12 + 14 + 21 + 28 + 42 = 140 (84)
1 + 2 + 4 + 8 + 11 + 22 + 44 = 92 (88)
1 + 2 + 3 + 5 + 6 + 9 + 10 + 15 + 18 + 30 + 45 = 144 (90)
1 + 2 + 3 + 4 + 6 + 8 + 12 + 16 + 24 + 32 + 48 = 156 (96)
1 + 2 + 4 + 5 + 10 + 20 + 25 + 50 = 117 (100)
1 + 2 + 3 + 6 + 17 + 34 + 51 = 114 (102)
1 + 2 + 4 + 8 + 13 + 26 + 52 = 106 (104)
1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 + 27 + 36 + 54 = 172 (108)
1 + 2 + 4 + 7 + 8 + 14 + 16 + 28 + 56 = 136 (112)
1 + 2 + 3 + 6 + 19 + 38 + 57 = 126 (114)

Problem 24

Permutation কি জিনিস সেটা তো সবাই জানেন

0, 1, 2 কে permutation করলে পাওয়া যাবে:
012
021
102
120
201
210

একইভাবে 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 কে permutation করলে পাওয়া যাবে:
0123456789
0123456798
0123456879
0123456897
0123456978
0123456987
0123457689
0123457698
0123457869
0123457896
0123457968
0123457986
0123458679
0123458697
0123458769
0123458796
0123458967
0123458976
0123459678
0123459687
….

এইভাবে করে লিখতে থাকেন। ঠিক আছে?
তারপর ১০০০০০০-তম লাইন যেটা হবে সেটাই উত্তর। :-O (মাইরালা! কেউ আম্রে মাইরালা)

0, 1, 2 permutation হল ৬ টা
0, 1, 2, 3, 4, 5, 6, 7, 8, 9 permutation কতগুলা জানেন? 3628800

কাজটা প্রথমে লুপ দিয়ে চিন্তা করার চেষ্টা করতে পারেন। আমার ধারনা লুপ দিয়ে চিন্তা করতে সহজ হবে।
তবে কোড করার ক্ষেত্রে recursive ভাবে করা সহজ। আমি দুইটা পদ্ধতি নিয়েই আলোচনা করব। আপাতত যেভাবে পারেন চিন্তা করে সলভ করেন আর কি।

Problem 25

১০০০ ডিজিটের প্রথম ফিবোনাচ্চি নাম্বারটা; কত তম ফিবোনাচ্চি নাম্বার, সেটাই উত্তর।

১০০০ ডিজিটের প্রথম ফিবোনাচ্চি নাম্বারটা দেখবেন?

107006626638275893676498058445739688508368389663215166501323520
337531452060469404062188914758248979265780469488817759195748433
646667256995951299603046126274809248218614406943305123477444275
027378175308757939166619214925918675955396642283714894311307469
950343954700198543260972306729019287052644724372611771582182554
849112052501320147861296593138179223555965745203950613755146783
754322911960212993404826070617539770684706820289548690266618543
512452190036948064135744747091170761976694569107009802439343961
747410373691250323136553216477369702316775505159517351846057995
491941096777837322966579658164651390348815425631018422419025984
608800011018625555024549393711365165703944762958471454852342595
042858242530608354443542821261100899286379504800689433030977321
783486454311320576565986845628861680871869383529735064398629764
066000072356291790520705116407761481249188583094594056668833910
935094445657635766615161931775379289166158132715961687748798382
1820492520348473874384736771934512787029218636250627816

বলতে হবে এটা কততম ফিবোনাচ্চি নাম্বার। সহজ না?

হুম। অনেক সহজ না, আবার কঠিনও বলা যাবে না। আমরা তো সবাই জানি বিগ-ইন্টিজার কিভাবে সলভ করতে হয়। সেইভাবে একটা একটা করে ফিবোনাচ্চি বের করতে থাকবেন। যখনই কোন ফিবোনাচ্চির দৈর্ঘ্য ১০০০ এর সমান/বেশি হবে তখনই উত্তরটা পেয়ে যাবেন।