UIU Competitive Programmers contest – 06 Solutions


All solutions written by: Rimon Mostafiz

A – Climbing Worm



#include <bits/stdc++.h>
using namespace std;

int n, u, d;

int solve(int n, int u, int d) {
    int climb = 0, minCnt = 0;
    while(climb < n) {
        climb += u;
        minCnt++;
        if (climb >= n) break;
        climb -= d;
        minCnt++;
    }

    return minCnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    while (cin >> n >> u >> d) {
        if(!n && !u && !d) break;
        cout << solve(n, u, d) << endl;
    }

    return 0;
}

B – Hello World!


#include <bits/stdc++.h>
using namespace std;

int n, Case = 0;

int solve(int n) {
    int cnt = 0, total = 1;
    while(total < n) {
        cnt++;
        total += total;
    }
    return cnt;
}

int main() {
    ios_base::sync_with_stdio(0);
    while (cin >> n) {
        if(n == -1) break;
        cout << "Case " << ++Case << ": " << solve(n) << endl;
    }

    return 0;
}

C – Binary Numbers


#include <bits/stdc++.h>
using namespace std;

int test, n;

void solve(int n) {
    bool space = false;
    for(int i = 0 ; i < 20 ; i++) {
        if(n & 1) {
            if(space) cout << " " << i;
            else { cout << i; space = true; }
        }
        n >>= 1;
    }
    cout << endl;
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> test;
    while (test--) {
        cin >> n;
        solve(n);
    }
    return 0;
}

D – Soundex


#include <bits/stdc++.h>
using namespace std;

#define MAX 1000

string st;
int ans[MAX + 7];

void solve(string st) {
    memset(ans, 0, sizeof ans);
    int x = 1;
    for(size_t i = 0 ; i < st.size() ; i++) {
        if(st[i] == 'A' || st[i] == 'E' || st[i] == 'I' || st[i] == 'O' || st[i] == 'U' || st[i] == 'H' || st[i] == 'W' ||st[i] == 'Y')
            ans[x++] = 0;
        else if(st[i] == 'B' || st[i] == 'F' || st[i] == 'P' || st[i] == 'V')
            ans[x++] = 1;
        else if(st[i] == 'C' || st[i] == 'G' || st[i] == 'J' || st[i] == 'K' || st[i] == 'Q' || st[i] == 'S' || st[i] == 'X' ||st[i] == 'Z')
            ans[x++] = 2;
        else if(st[i] == 'D' || st[i] == 'T')
            ans[x++] = 3;
        else if(st[i] == 'L')
            ans[x++] = 4;
        else if(st[i] == 'M' || st[i] == 'N')
            ans[x++] = 5;
        else if(st[i] == 'R')
            ans[x++] = 6;
    }

    for(int i = 1 ; i < x ; i++) {
        if(ans[i] && ans[i] != ans[i-1]) cout << ans[i];
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(0);
    while (cin >> st) {
        solve(st);
    }

    return 0;
}

E – Arbiter Login


#include <bits/stdc++.h>
using namespace std;

int test, Case = 0;
string str1, str2, STR1, str, STR;

string capsLock(string s) {
    string st = s;
    for (size_t i = 0 ; i < s.size() ; i++) {
        if (s[i] >= 'a' && s[i] <= 'z') st[i]-=32;
        if (s[i] >= 'A' && s[i] <= 'Z') st[i]+=32;
    }
    return st;
}

string numLock(string s) {
    string st="";
    for (size_t i = 0 ; i < s.size() ; i++)
        if (s[i] < '0' || s[i] > '9') st += s[i];
    return st;
}

void solve(string str1, string str2) {

    if (str1 == str2) cout << "Login successful.";
    else if (STR1 = capsLock(str1), STR1 == str2) cout << "Wrong password. Please, check your caps lock key.";
    else if (str  = numLock (str1), str  == str2) cout << "Wrong password. Please, check your num lock key.";
    else if (STR  = capsLock (str), STR  == str2) cout << "Wrong password. Please, check your caps lock and num lock keys.";
    else cout << "Wrong password.";


}

int main() {
    ios_base::sync_with_stdio(0);
    cin >> test;
    while(test--) {
        cin >> str1 >> str2;
        cout << "Case " << ++Case << ": ";
        solve(str1, str2);
        cout << endl;
    }
    return 0;
}

UIU Competitive Programmers contest – 05 Solutions


A – Word Reversal


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>

using namespace std;

char input [1000];

void reverseIt(int start, int end)
{
    for (int i = end - 1; i >= start; i--)
        printf ("%c", input [i]);
}

void printOutput()
{
    int length = strlen(input);
    int start = 0;
    bool space = false;

    for (int i = 0; i <= length; i++ ) {
        if (input [i] == ' ' || input [i] == '\0') {

            if (space) printf (" ");
            space = true;

            reverseIt(start, i);
            start = i + 1;
        }
    }

    printf ("\n");
}

int main(int argc, const char * argv[])
{
    int testCases;
    scanf ("%d", &testCases);

    bool blankLine = false;

    while (testCases--) {

        // There is a blank line between output blocks.
        if (blankLine) printf ("\n");
        blankLine = true;

        int n;

        scanf ("%d", &n);

        // gets will take the \n character after integer input
        // do not use fflush(), always use getchar() 
        getchar();

        while(n--) {
            gets(input);
            printOutput();
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE

B – Easier Done Than Said?


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>

using namespace std;

char password [20 + 10];
int length;

bool isVowel(char x) {
    return x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u';
}


bool isConsonant(char x) {
    return !isVowel(x);
}

bool atLeastOneVowel() {

    for (int i = 0; i < length; i++) {
        if (isVowel(password [i])) return true;
    }

    return false;
}

bool threeConsecutive() {

    for (int i = 2; i < length; i++) {
        if (isVowel(password [i]) && isVowel(password[i - 1]) && isVowel(password [i - 2])) return true;
        if (isConsonant(password [i]) && isConsonant(password[i - 1]) && isConsonant(password [i - 2])) return true;
    }

    return false;
}

bool twoConsecutive() {

    for (int i = 1; i < length; i++) {
        if (password [i] == password [i - 1] && password [i] != 'e' && password [i] != 'o') return true;
    }

    return false;
}

int main(int argc, const char * argv[])
{
    while(scanf ("%s", password)) {

        if (strcmp(password, "end") == 0) break;

        length = strlen(password);

        if (atLeastOneVowel() && !threeConsecutive() && !twoConsecutive()) {
            printf ("<%s> is acceptable.\n", password);

        } else {
            printf ("<%s> is not acceptable.\n", password);
        }
    }

    return 0;
}

// @END_OF_SOURCE_CODE

C – Team


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

using namespace std;


int main(int argc, const char * argv[])
{
    int n;

    scanf ("%d", &n);

    int a;
    int b;
    int c;

    int cnt = 0;

    for ( int i = 0; i < n; i++ ) {
        scanf ("%d %d %d", &a, &b, &c);

        if (a + b + c >= 2) cnt++;
    }

    printf ("%d\n", cnt);

    return 0;
}

// @END_OF_SOURCE_CODE

D – Hungry Sequence


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cmath>

using namespace std;

bool isPrime(int n)
{
    if ( n < 2 ) return false;

    if (n == 2) return true;

    if (n % 2 == 0) return false;

    int squareRoot = (int) sqrt(n);

    for ( int i = 3; i <= squareRoot; i += 2) {
        if (n % i == 0) return false;
    }

    return true;
}

int getNextPrime(int n) {

    n++;

    while(!isPrime(n)) {
        n++;
    }

    return n;
}


int main(int argc, const char * argv[])
{
    int n;

    scanf ("%d", &n);

    bool space = false;

    int prime = 2;

    for ( int i = 0; i < n; i++ ) {
        if (space) printf (" ");
        space = true;

        printf ("%d", prime);

        prime = getNextPrime(prime);
    }

    printf ("\n");

    return 0;
}

// @END_OF_SOURCE_CODE

D – Hungry Sequence (Alternate solution)


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

using namespace std;


int main(int argc, const char * argv[])
{
    int n;

    scanf ("%d", &n);

    bool space = false;

    int ans = n;

    for ( int i = 0; i < n; i++ ) {
        if (space) printf (" ");
        space = true;

        printf ("%d", ans++);
    }

    printf ("\n");

    return 0;
}

// @END_OF_SOURCE_CODE

E – AC Me


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>
#include <cstring>

using namespace std;

int main(int argc, const char * argv[])
{
    int frequency [26 + 5];

    char input [100000 + 10];

    while(gets(input)) {
        memset(frequency, 0, sizeof frequency);

        int length = strlen(input);

        for (int i = 0; i < length; i++) {
            frequency [input [i] - 'a']++;
        }

        for (int i = 0; i < 26; i++) {
            printf ("%c:%d\n", 'a' + i, frequency [i]);
        }

        printf ("\n");
    }


    return 0;
}

// @END_OF_SOURCE_CODE

UIU Competitive Programmers contest – 04 Solutions


All solutions written by: Rimon Mostafiz

A-Odd Sum


#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int test, Case = 0;
    cin >> test;
    while(test--) {
        int l, r, odd_sum = 0;
        cin >> l >> r;
        for(int i=l; i<=r; i++) {
            if(i%2) odd_sum += i;
        }

        cout << "Case " << ++Case << ": " << odd_sum << endl;
    }
    return 0;
}

B-One-Two-Three


#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int test;
    cin >> test;
    while(test--) {
        string st;
        cin >> st;
        if(st.size()==5) cout << 3 << endl;
        else {
            int cnt = 0;
            if(st[0]=='o') cnt++;
            if(st[1]=='n') cnt++;
            if(st[2]=='e') cnt++;

            if(cnt>=2) cout << 1 << endl;
            else cout << 2 << endl;
        }
    }
    return 0;
}

C-Nasty Hacks


#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int test;
    cin >> test;
    while(test--) {
        int r, e, c;
        cin >> r >> e >> c;
            if(e-c < r) cout << "do not advertise" << endl;
            else if(e-c > r) cout << "advertise" << endl;
            else cout << "does not matter" << endl;
        }
    return 0;
}

D-Misspelling


#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    int test, Case = 0;
    cin >> test;
    while(test--) {
        int n;
        string st;
        cin >> n >> st;
        st.erase(st.begin() + n-1);
        cout << ++Case<< " " <<st << endl;
    }
    return 0;
}

E-Summing Digits


#include <cstdio>
#include <iostream>

using namespace std;

int recur (int n) {
    if(n<10) return n;
    int ret = 0;
    while(n) {
        ret += n % 10;
        n /= 10;
    }
    return recur(ret);
}

int main() {
    ios_base::sync_with_stdio(0);
    int n;
    while(cin >> n && n) {
        cout << recur(n) << endl;
    }
    return 0;
}

UIU: Learn C by Examples: Part: 5



#include <cstdio>
#include <cstring>
#include <queue>

#define ROW 10  // number of Rows in the plane 
#define COL 10  // number of Columns in the plane 

struct node {
    int xPos;   // position of x-coordinate 
    int yPos;   // position of y-coordinate 
    int val;    // number of moves 

    node() {}

    node(int a, int b, int c) {
        xPos = a;
        yPos = b;
        val = c;
    }
};

using namespace std;

// visited node
bool visit [ROW] [COL];

// movement values
int moves [ROW] [COL];

// Checks to see if a particular coordinate is valid 
// we will not consider any negative coordinates 
// for example, (-1, -1) is invalid coordinate 
bool isValid(int xPos, int yPos) {
    if (xPos < 0) return false;
    if (xPos >= ROW) return false;
    if (yPos < 0) return false;
    if (yPos >= COL) return false;

    return true;
}

int main ()
{
    int sourceX, sourceY;
    int destinationX, destinationY;

    // sample value
    sourceX = 1;
    sourceY = 1;

    destinationX = 9;
    destinationY = 9;
    
    memset(visit, false, sizeof visit);
    memset(moves, -1, sizeof moves);

    queue<node> q;
    q.push(node(sourceX, sourceY, 0));
    visit [sourceX] [sourceY] = true;

    // horses move
    int dr [] = {1, 2, 2, 1, -1, -2, -2, -1};
    int dc [] = {2, 1, -1, -2, -2, -1, 1, 2};

    while(!q.empty()) {
        node pop = q.front();
        q.pop();

        if (pop.xPos == destinationX && pop.yPos == destinationY) {
            printf ("number of moves: %d\n", pop.val);
        }

        moves [pop.xPos] [pop.yPos] = pop.val;

        for ( int i = 0; i < 8; i++ ) {
            int newX = pop.xPos + dr [i];
            int newY = pop.yPos + dc [i];
            int newVal = pop.val + 1;

            // if the new position is not valid or 
            // we have been visited it before then 
            // there is no need to push it again in queue 
            if (isValid(newX, newY) && !visit [newX] [newY]) {
                // this node hasn't been visited yet
                visit [newX] [newY] = true;
                q.push(node(newX, newY, newVal));
            }
        }
    }

    // prints the number of moves needed for each coordinates 
    for ( int i = 0; i < ROW; i++ ) {
        for ( int j = 0; j < COL; j++ ) {
            printf ("%d\t", moves [i] [j]);
        }
        printf ("\n");
    }

    return 0;
}

UIU: Learn C by Examples: Part: 1


Question 1:

Write a program that will output the greatest number between two numbers


#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{

    int firstNumber;
    int secondNumber;

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

    if (firstNumber > secondNumber) {
        printf ("%d\n", firstNumber);

    } else {
        printf ("%d\n", secondNumber);
    }

    return 0;
}

Question 2:

Write a program that will output the smallest number between two numbers. (try yourself)

Question 3:

Write a program that will output the greatest number among three numbers


#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{

    int firstNumber;
    int secondNumber;
    int thirdNumber;

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

    if (firstNumber > secondNumber) {
        if (firstNumber > thirdNumber) {
            printf ("%d\n", firstNumber);

        } else {
            printf ("%d\n", thirdNumber);

        }
    } else {
        if (secondNumber > thirdNumber) {
            printf ("%d\n", secondNumber);

        } else {
            printf ("%d\n", thirdNumber);

        }
    }

    return 0;
}


#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{

    int firstNumber;
    int secondNumber;
    int thirdNumber;

    scanf ("%d %d %d", &firstNumber, &secondNumber, &thirdNumber);
    
    if (firstNumber > secondNumber && firstNumber > thirdNumber) {
        printf ("%d\n", firstNumber);
        
    } else if (secondNumber > firstNumber && secondNumber > thirdNumber) {
        printf ("%d\n", secondNumber);
        
    } else {
        printf ("%d\n", thirdNumber);
    }

    return 0;
}

Question 4:

Write a program that will output the smallest number among three numbers (try yourself in both mentioned ways showed in Question 3 solution)

Question 5:

Write a program that will output two numbers in sorted order (descending order: greater number will come first)


#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{

    int firstNumber;
    int secondNumber;

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

    if (firstNumber > secondNumber) {
        printf ("%d %d\n", firstNumber, secondNumber);
        
    } else {
        printf ("%d %d\n", secondNumber, firstNumber);
    }
    

    return 0;
}

Question 6:

Write a program that will output two numbers in sorted order (ascending order: smaller number will come first) [try yourself]

Question 7:

Write a program that will output three numbers in sorted order (descending order: greater number will come first)


// @BEGIN_OF_SOURCE_CODE

#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{

    int firstNumber;
    int secondNumber;
    int thirdNumber;

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

    if (firstNumber > secondNumber) {
        if (firstNumber > thirdNumber) {
            if (secondNumber > thirdNumber) {
                printf ("%d %d %d", firstNumber, secondNumber, thirdNumber);

            } else {
                printf ("%d %d %d", firstNumber, thirdNumber, secondNumber);

            }
        } else {
            printf ("%d %d %d", thirdNumber, firstNumber, secondNumber);

        }
    } else if (secondNumber > thirdNumber) {
        if (firstNumber > thirdNumber) {
            printf ("%d %d %d", secondNumber, firstNumber, thirdNumber);

        } else {
            printf ("%d %d %d", secondNumber, thirdNumber, firstNumber);

        }
    } else {
        if (firstNumber > secondNumber) {
            printf ("%d %d %d", thirdNumber, firstNumber, secondNumber);

        } else {
            printf ("%d %d %d", thirdNumber, secondNumber, firstNumber);

        }
    }

    printf ("\n");

    return 0;
}

// @END_OF_SOURCE_CODE

Question 8:

Write a program that will output three numbers in sorted order (ascending order: greater number will come first) [try yourself]

Question 9:

Write a program that will output “Yes” if two numbers are distinct (different, not same)


#include <cstdio>

using namespace std;

int main(int argc, const char * argv[])
{

    int firstNumber;
    int secondNumber;

    scanf ("%d %d", &firstNumber, &secondNumber);
    
    if (firstNumber != secondNumber) {
        printf ("Yes\n");
        
    } else {
        printf ("No\n");
        
    }

    return 0;
}

Question 10:

Write a program that will output “Yes” if three numbers are distinct (different, not same)

try yourself and check these input against your code


1 1 1
No

1 1 2
No

2 1 1
No

3 4 3
No

4 5 2
Yes

Question 11:

Write a program that will output the greatest number between

two numbers and
three numbers and
an array of numbers

using overloading function (same function name, but different parameter)


#include <cstdio>

using namespace std;

/**
* return the greatest number between two numbers
*/
int maximum(int a, int b)
{
    if (a > b) return a;    // if 'a' is greater then just return 'a'
    return b;               // otherwise, return 'b'
}

/**
* return the gretest number among three numbers
*/
int maximum(int a, int b, int c)
{
    return maximum(a, maximum(b, c));
}

int maximum(int a [], int length)
{
    int ret = 0;

    for ( int i = 0; i < length; i++ ) {
        ret = maximum(ret, a [i]);
    }

    return ret;
}

int main(int argc, const char * argv[])
{
    int a = 10, b = 15, c = 25;

    int array [] = {3, 6, 2, 1, 9, 8};

    printf ("%d\n", maximum(a, b));

    printf ("%d\n", maximum(a, b, c));

    printf ("%d\n", maximum(array, 5));

    return 0;
}

UIU: Learn C by Examples


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

আমাদের এখানে ২ ধরনের উদাহরন থাকবে।
১ম, একটা প্রোগ্রামিং প্রবলেম থাকবে। সেটার কোড করতে হবে
২য়, একটা কোড দেয়া থাকবে, সেটার আউটপুট বের করতে হবে।

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

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

কোনকিছু বুঝতে সমস্যা হলে নিজে চেষ্টা করেন। একেবারেই না পারলে স্যার/ম্যাম বা বড় ভাই/আপু-কে জিজ্ঞেস করতে পারেন। আমাকে জিজ্ঞেস করে কোনই লাভ নাই। আমি এইগুলা পারি না।

|| UIU: Learn C by Examples Part – 1 ||

UIU: Learn C by Examples Part – 2 ||

UIU: Learn C by Examples Part – 3 || prime factor, gcd, lcm, palindrome

UIU: Learn C by Examples Part – 4 || preprocessor, sieve,

|| UIU: Learn C by Examples : Declarations and Initializations ||

|| UIU: Learn C by Examples : Control Instructions ||

|| UIU: Learn C by Examples : Expressions ||

|| UIU: Learn C by Examples : Functions ||

|| UIU: Learn C by Examples : C Preprocessor ||

|| UIU: Learn C by Examples : Pointers ||

|| UIU: Learn C by Examples : Arrays ||

|| UIU: Learn C by Examples : String ||

|| UIU: Learn C by Examples : Reverse ||

|| Program examples with all-together ||

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;
}

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

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