Programming Solutions

Monday, April 24, 2017

Bubble Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Bubble-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[50],n,i,j,temp;
    cin>>n; // Enter the number of element
    for(i=0; i<n; i++) cin>>a[i]; // Enter all elements
    for(i=1; i<n; i++){
        for(j=0; j<(n-i); j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
    for(i=0; i<n; i++) cout<<a[i]<<" ";
    cout<<endl;
    return 0;
}

Quick Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Quick-Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int ar[1000];

int partition (int low, int high){
    int pivot=ar[high];
    int i=(low-1);
    for(int j=low; j<high; j++){
        if(ar[j]<=pivot){
            i++;
            swap(ar[i],ar[j]);
        }
    }
    swap(ar[i+1], ar[high]);
    return (i+1);
}

void quickSort(int low, int high){
    if(low<high){
        int pi=partition(low, high);
        quickSort(low, pi-1);
        quickSort(pi+1, high);
    }
}

int main(){
    int n,i;
    cin>>n;
    for(i=0;i<n;i++) cin>>ar[i];
    quickSort(0, n-1);
    for(i=0; i<n; i++) cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}

Merge Sort - Implementation with C++

/*  Bismillahir Rahmanir Rahim
    Implementation of Merge Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;
int ar[1000];

int marg_partition(int st, int mid , int ed){
    int arr[1000], left, right, j=0, i;
    left=st;
    right=mid+1;
    while(left<=mid && right<=ed){
        if(ar[left]<ar[right]){
            arr[j++]=ar[left];
            left++;
        }
        else{
            arr[j++]=ar[right];
            right++;
        }
    }
    if(left>mid){
        for(i=right;i<=ed;i++)
            arr[j++]=ar[i];
    }
    else {
        for(i=left;i<=mid;i++)
            arr[j++]=ar[i];
    }
    for(i=0;i<j;i++) ar[i+st]=arr[i];
    return 0;
}

int marg_sort(int st,int ed){
    if(st<ed){
        int mid=(st+ed)/2;
        marg_sort(st,mid);
        marg_sort(mid+1,ed);
        marg_partition(st,mid,ed);
    }
}

int main(){
    int i,j,n,k;
    cin>>n;
    for(i=0;i<n;i++) cin>>ar[i];

    marg_sort(0,n-1);
    for(i=0;i<n;i++) cout<<ar[i]<<" ";
    cout<<endl;
    return 0;
}

Insertion Sort - C++ Implementation

Try to understand the following procedure.

77 33 44 11 88 22 66 55

33 77 . . . . . . . . . . . . . . . . . .
33 44 77 . . . . . . . . . . . . . . .
11 33 44 77 . . . . . . . . . . . .
11 33 44 77 88 . . . . . . . . .
11 22 33 44 77 88 . . . . . .
11 22 33 44 66 77 88 . . .
11 22 33 44 55 66 77 88

The following Code represent the concept.

/*  Bismillahir Rahmanir Rahim
    Implementation of Insertion Sort using C++
*/
#include<bits/stdc++.h>
using namespace std;

int main(){
    int ar[100000], n, i, j, key;
    cin>>n;  // number of elements
    for(i=0; i<n; i++) cin>>ar[i]; // input elements one by one
    
    for(i=1; i<n; i++){ // starting from 2nd element
        key=ar[i]; 
        j=i-1; 
        while(j>=0 && key<ar[j]){ //comparing key with all previous
            ar[j+1]=ar[j]; 
            j--;
        }
        ar[j+1]=key; 
    }
    
    for(i=0;i<n;i++) cout<<ar[i]<<" ";
    return 0;
}

Friday, April 7, 2017

Random Value Generator in C++

/*  Bismillahir Rahmanir Rahim
    Random Value Generating
    Input any integer(n).
*/
#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
     int n;
     while(cin>>n){// for understanding the output clearly
         cout<<"Random value (any integer)   = "<<rand()<<endl;
         cout<<"Random value (from 0 to 9)   = "<<rand()%10<<endl;
         cout<<"Random value (from 1 to 100) = "<<rand()%100+1<<endl;
         cout<<"Random value (from 3 to 8)   = "<<rand()%6+3<<endl;
     }
     return 0;
}

Thursday, March 23, 2017

BigMod and BigsumMod

/*  Bismillahir Rahmanir Rahim
    BigMod of Series:
    (1 + b + b^2 + b^3 + b^4 +......+ b^(p-1) )%mod
*/

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll b, p, m;

ll bigmod(ll b, ll p, ll m){ // its the BigMod
    if(p==0) return 1;
    ll x=bigmod(b, p/2, m);
    x=(x*x)%m;
    if(p%2==1) x=(x*b)%m;
    return x;
}

ll bigsummod(ll b, ll p, ll m){ // mod in every line
    if(p==2) return (1+b)%m;  // when 2 term (1+b)
    else if(p==3) return (1+b+b*b)%m;
    else if(p%2==1) return (1+b*bigsummod(b, p-1, m))%m;
    else{
       ll xx=bigsummod(b, p/2, m)%m;
       return xx=(xx+(bigmod(b, p/2, m)*xx))%m;
    }
}

int main(){
    while(cin>>b>>p>>m){ // b=Base, p=power+1(number of term), m=mod
        cout<<bigsummod(b, p, m)<<endl;
    }
    return 0;
}

Wednesday, March 22, 2017

Factorial এর Digit সংখ্যা

যদি 100!(বা এর চেয়ে বড়) এর digit সংখ্যা বের করতে বলে সেক্ষেত্রে 100! এর মান বের করে digit count করব ?না, খুব মজার উপায় আছে। এই ক্ষেত্রে আমাদের সাহায্য করবে log, অনেক মজার একটা জিনিস, যত একে চিনছি ততই মজা পাচ্ছি। calculator এ log(10)=1, log(100)=2, log(105)=2.021189299, log(1000)=3 । ঘটনা কি ঘটছে এতক্ষণে বুঝে ফেলার কথা । 100 এর digit সংখ্যা = log(100)+1 = 3. এটাতো একটা সংখ্যার জন্য পেলাম কিন্তু আমাদের লাগবে 100! এর জন্য। log এর ছোটবেলার সূত্র ভুলে গেলে চলবে না log(a*b)=log(a)+log(b).
100! = 100*99*98*97*.......................*2*1
100! এর digit সংখ্যা = log(100)+log(99)+................+log(2)+log(1).
এই কাজ calculator এ মান ঠিক এই রকম আসলেও code এর compiler এ কিন্ত ঠিক এমন আসে না । এর কারণ হল calculator এ log এর মানটা আসলে 10 ভিত্তিক log এর মান। আর আমাদের সাধারণ Number System হল 10 ভিত্তিক । compiler এ log এর যে মান আসছে সেই মানকে log(10) দ্বারা ভাগ করলে 10 ভিত্তিক