CODEblog

Doubly Linked List | Data Structure

noreply@blogger.com (Mahmudul Hasan) — Fri, 23 Jul 2021 16:51:00 +0000

image source: medium.com

***Table of contents***

1. Doubly Linked List Structure.

2. Creating a Doubly Linked List with the given size.

3. Printing the Doubly Linked List.

4. Length of the Linked List.

5. Insertion of a node at Linked List.

6. Deletion of all nodes containing a particular value from the Linked List.

7. Reversing the Doubly Linked List.

CODE in C/C++:

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

//1.Doubly Linked List structure
typedef struct Node{
    Node* prev;
    int data;
    Node* next;
}Node;
//2.
/**
 * @brief Creates a Doubly Linked List with given size.
 * 
 * @param n - the length of the Linked List
 * @return Node* 
 */
Node* Create_DLL(int n){
    Node* head=nullptr,*tail=nullptr;
    int data;
    while (n--)
    {
        cin>>data;
        if(!head){
            head = (Node*)malloc(sizeof(Node));
            head->data = data;
            head->prev = head->next = nullptr;
            tail = head;
            continue;
        }
        Node* t = (Node*)malloc(sizeof(Node));
        t->data = data;
        t->prev = tail;
        t->next = nullptr;
        tail->next = t;
        tail = t;
    }
    return head;
}

//3. Prints the linked list
void Display(Node* head){
    if(!head){
        cout<<endl;
        return;
    }
    cout<<head->data<<" ";
    Display(head->next);
}

//4.
/**
 * @brief Returns the doubly linked list's length
 * 
 * @param head 
 * @return int 
 */
int length(Node* head){
    int l = 0;
    Node* cur = head;
    while(cur){
        ++l;
        cur = cur->next;
    }
    return l;
}

//5.
/**
 * @brief Inserts a node in the linked list
 * 
 * @param head 
 * @param data 
 * @param pos 
 * @return Node* 
 */
Node* InsertNodeAtDLL(Node* head, int data, int pos){
    Node* t = (Node*) malloc(sizeof(Node));
    t->data = data;
    if(pos<=0){
        t->prev = nullptr;
        t->next = head;
        head->prev = t;
        head = t;
        return head;
    }
    else if(pos>0 and pos<length(head)){
        Node* q=head,*p=head;
        for(int i=1; i<=pos; ++i){
            q = p;
            p = p->next;
        }
        if(p){
            t->prev = q;
            t->next = p;
            q->next = t;
            p->prev = t;
        }
    }
    else{
        Node* q=head,*p=head;
        while (p->next)
        {
            p = p->next;
        }
        t->next = nullptr;
        t->prev = p;
        p->next = t;
    }
    return head;
}
//6.
/**
 * @brief Deletes all the nodes from the Linked list with  the given value.
 * 
 * @param head 
 * @param data 
 * @return Node* 
 */
Node* DeleteNodeFromDLL(Node* head, int data){
    Node* p = head,*q=head;
    while(p){
        if(p->data==data && p==q){
            head = head->next;
            p = q = head;
            continue;
        }
        else if(p->data==data){
            if(p->next){
                q->next = p->next;
                p->next->prev = q;
                p = q;
            }
            else{
                q->next = nullptr;
            }
            
        }
        q = p;
        p = p->next;
    }
    return head;
}
//7.
/**
 * @brief Reverses the Doubly Linked List
 * 
 * @param head 
 * @return Node* 
 */
Node* ReverseDLL(Node* head){
    Node* t,*p;
    while(head){
        t = head->next;
        head->next = head->prev;
        head->prev = t;
        head = head->prev;
        if(head!=nullptr and head->next==nullptr){
            p = head;
        }
    }
    return p;
}

int main()
{
    int n;
    cout<<"Enter the length of the Linked List: ";
    cin>>n;
    Node* head = Create_DLL(n);
    Display(head);



    int val,pos;
    cout<<"Enter the value to insert: ";
    cin>>val;
    cout<<"Enter the position to insert: ";
    cin>>pos;
    head = InsertNodeAtDLL(head, val, pos);
    Display(head);
    
    

    cout<<"Enter the data you want to delete: ";
    cin>>val;
    head = DeleteNodeFromDLL(head,val);
    Display(head);

    head = ReverseDLL(head);
    Display(head);


    free(head);
    return 0;
}

Cycle Detection in a Linked List | Data Structure

noreply@blogger.com (Mahmudul Hasan) — Thu, 22 Jul 2021 20:03:00 +0000

Problem: Our task is to determine is there any loop/cycle in a Linked List or not?

Required Knowledge: Singly Linked List | Data Structure

Explanation:

image source: hackerrank.com

There is a "slow" pointer that moves one node at a time. There is a "fast" pointer that moves twice as fast, two nodes at a time.

A visualization as slow and fast pointers move through the linked list with 10 nodes:

1: |sf--------|
2: |-s-f------|
3: |--s--f----|
4: |---s---f--|
5: |----s----f|

At this point one of two things is true:

1) the linked list does not loop (checked with fast != null && fast.next != null && slow!=null) or

2) it does loop. Let's continue visualization assuming it does loop:

6: |-f----s---|
7: |---f---s--|
8: |-----f--s-|
9: |-------f-s|
10: s == f

If the linked list is not looped, the fast pointer finishes the race at O(n/2) time; we can remove the constant and call it O(n). If the linked list does loop, the slow pointer moves through the whole linked list and eventually equals the faster pointer at O(n) time.

CODE in C++:

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


/*1. Single Linked List Structure*/
typedef struct Node{
    int data;
    Node* next;
}Node;


/*Creates a Linked List with the given size*/
Node* Create_SingleLL(int n){
    int data;
    Node *head=nullptr,*tail=nullptr;
    while(n--){
        cin>>data;
        if(!head){
            head = (Node*)malloc(sizeof(Node));
            head->data = data;
            head->next = nullptr;
            tail = head;
            continue;
        }
        Node* t = (Node*) malloc(sizeof(Node));
        t->data = data;
        t->next = nullptr;
        tail->next = t;
        tail = t;
    }
    //creates a cycle
    tail->next = head;
    return head;
}



/**
 * @brief dertermines is there any loop/cycle in the linked list
 * To Understand this you can assume a variable slow as tortoise and fast as a hare.
 * If there exists a cycle in the linked list,  before reaching the slow of the last node of the list
 * the fast will will meet the slow, otehrwise not.
 * 
 * @param head 
 * @return true 
 * @return false 
 */
bool IsCycle(Node* head){
    if(!head) return false;

    Node* slow = head, *fast=head;
    while(slow && fast && fast->next ){
        slow = slow->next;
        fast = fast->next->next;
        if(slow==fast) return true;
    }
    return false;
}




int main(){
    int n;
    cout<<"Enter the length of the Linked List: ";
    cin>>n;
    Node* head = Create_SingleLL(n);//creates a cycle, 
                                    //the last node is connected 
                                    //with the first node.
    if(IsCycle(head)) cout<<"Cycle Exists!\n";
    else cout<<"There is no Cycle in the linked list!\n";

    free(head);
    return 0;
}

Singly Linked List | Data Structure

noreply@blogger.com (Mahmudul Hasan) — Thu, 22 Jul 2021 19:24:00 +0000

Singly Linked List- Code on PasteBin

image source: javapoint.com

***Table of contents***

1. Single Linked List Structure.

2. Creating a Linked List with the given size.

3. Printing the linked list.

4. Length of the Linked list.

5. Determining the Sum of the elements of the linked list.

6. Finding the min element of LL.

7. Finding the max element of LL.

8. Searching a data/value of a node in the LL.

9. Searching a node with its data in the Linked List and 

   making it the head/root node.

10. Insertion of a node at Linked List.

11. Deletion of a node from Linked List.

12. Reversing the Linked List.

CODE in C/C++:

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


/*1. Single Linked List Structure*/
typedef struct Node{
    int data;
    Node* next;
}Node;


/*2. Creates a Linked List with the given size*/
Node* Create_SingleLL(int n){
    int data;
    Node *head=nullptr,*tail=nullptr;
    while(n--){
        cin>>data;
        if(!head){
            head = (Node*)malloc(sizeof(Node));
            head->data = data;
            head->next = nullptr;
            tail = head;
            continue;
        }
        Node* t = (Node*) malloc(sizeof(Node));
        t->data = data;
        t->next = nullptr;
        tail->next = t;
        tail = t;
    }
    return head;
}


/*3. Prints the linked list*/
void Display(Node* head){
    Node* curr = head;
    while(curr){
        cout<<curr->data<<" ";
        curr = curr->next;
    }
    cout<<endl;
}


/*4. Length of the LL*/
int Length_SLL(Node* head){
    Node* x = head;
    int l = 0;
    while (x)
    {
        ++l;
        x = x->next;
    }
    return l;
}


//***5***
/**
 * @brief Sum of the elements of the linked list
 * 
 * @param head - the root node
 * @return long 
 */

long Sum(Node* head){
    if(!head) return 0LL;
    return head->data*1LL+Sum(head->next);
}


//***6*** 
/**
 * @brief Returns the min element of LL
 * 
 * @param p - the root node
 * @return minmum value
 */

int Minimum(Node* p){
    int mn = INT_MAX;
    while (p){
        if(p->data <mn) mn = p->data;
        p = p->next;
    }
    return mn;
}


//***7***
/**
 * @brief Returns the max element of LL
 * 
 * @param p - the root node
 * @return maximum value
 */

int Maximum(Node* p){
    int mx = INT_MIN;
    while (p){
        if(p->data>mx) mx = p->data;
        p = p->next;
    }
    return mx;
}


//***8***
/**
 * @brief Searches a data in the LL
 * If found, returns the node, else nullptr
 * 
 * @param p - the root node
 * @param data - the value that we want to search
 * @return Node* - the node that we're searching for
 */

Node* Search(Node* p, int data){
    if(!p) return NULL;
    else if(p->data == data) return p;
    return Search(p->next, data);
}


//***9***
/**
 * @brief Search a node in the Linked List and makes it as Head/root node
 * 
 * @param head - the root node
 * @param data 
 * @return Node* 
 */

Node* SearchAndMakeAsHead(Node* head, int data){
    Node* q=nullptr;
    Node* p = (Node*)malloc(sizeof(Node));
    p = head;
    while(p){
        if(p->data==data){
            q->next = p->next;
            p->next = head;
            head = p;
            return p;
        }
        q = p;
        p = p->next;
    }
    return head;
}
/*10. Inserts a node at Linked List*/
/**
 * @brief here we're considering the linked list as 0 base, 
 * means the starting position of the linked list is 0.
 * 
 * @param head - the root node
 * @param data - the value of the node
 * @param pos - where the node will be inserted
 */

Node* InsertNodeAtSLL(Node* head, int data, int pos){
    Node* t,*p;
    t = (Node*)malloc(sizeof(Node));
    if(pos==0){
        t->data = data;
        t->next = head;
        head = t;
    }
    else if(pos>0 && pos<=Length_SLL(head)){
        p = head;
        for(int i=1; i<pos; ++i){
            p = p->next;
        }
        if(p){
            t->data = data;
            t->next = p->next;
            p->next = t;
        }
    }
    return head;
}

//***11***

/**
 * @brief Deletes a node from the given position of a Linked List
 * Assume that the starting position of the linked list is 0
 * 
 * @param head - the root node
 * @param pos - the position of the node that we want to delete
 * @return Node* 
 */
Node* DeleteNodeFromSLL(Node* head, int pos){
    
    if(pos==0){
        head = head->next;
        return head;
    }
    else if(pos>0 && pos<Length_SLL(head)){
        Node* p,*q;
        p = head;
        for(int i=0; i<pos; ++i){
            q = p;
            p = p->next;
        }
        if(p){
            q->next = p->next;
        }
    }
    return head;
}


//***12***
/**
 * @brief Reverses the Single linkedlist
 * 
 * @param head - the root node
 * @return Node* 
 */

Node* ReverseSLL(Node* head){
    if(!head->next) return head;
    Node* t = ReverseSLL(head->next);
    head->next->next = head;
    head->next = nullptr;
    return t;
}


int main(){

    int n, x, y;
    cin>>n;
    Node* head = Create_SingleLL(n);
    Display(head);
    cout<<"Length: "<<Length_SLL(head)<<endl;
    cout<<"Sum: "<<Sum(head)<<endl;
    cout<<"Max element: "<<Maximum(head)<<endl;
    cout<<"Min Element: "<<Minimum(head)<<endl;
    

    cout<<"Enter the value you that want to search: ";
    cin>>x;
    Node* src = Search(head, x);
    if(src)cout<<"Found!\n";
    else cout<<"Not Found!\n";

    head = SearchAndMakeAsHead(head, x);
    Display(head);
    

    cout<<"Enter the position of assertion: ";
    cin>>y;
    cout<<"Enter the value of the Node that you want to Insert: ";
    cin>>x;
    head = InsertNodeAtSLL(head, x, y);
    Display(head);

    cout<<"Enter the position of deletion: ";
    cin>>x;
    head = DeleteNodeFromSLL(head, x);
    Display(head);


    head = ReverseSLL(head);
    Display(head);



    free(head);
    return 0;
}

Factorial of 500!

noreply@blogger.com (Mahmudul Hasan) — Sat, 03 Apr 2021 06:31:00 +0000

Problem link: UVa 623 - 500!

HackerRank - Extra Long Factorial

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

int main()
{

    
    int n;

    while (cin >> n)
    {
        int arr[1000000];
        int carry = 0, k = 0;
        arr[0] = 1;

        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j <= k; ++j)
            {
                arr[j] = arr[j] * i + carry;
                carry = arr[j] / 10;
                arr[j] = arr[j] % 10;
            }
            while (carry)
            {
                k++;
                arr[k] = carry % 10;
                carry /= 10;
            }
        }

        cout << n << "!" << endl;
        for (int i = k; i >= 0; --i)
            cout << arr[i];
        cout << endl;
    }

    return 0;
}

Uses of FILE pointer and Text File manipulation through C code

noreply@blogger.com (Mahmudul Hasan) — Wed, 10 Mar 2021 08:19:00 +0000

#include"stdio.h"
#include"string.h"
#include"stdlib.h"

char *Update(char *s, char *prev, char *new)
{
    int pLength = strlen(prev);
    int nLength = strlen(new);
    int count=0;
    int i;

    for(i=0; s[i]!='\0';++i)
    {
        if(strstr(&s[i],prev)== &s[i]){
            ++count;
            i=i+pLength-1;
        }
    }
    
    char *replace = (char *)malloc(i+count*(nLength-pLength)+1);

    i=0;
    while (*s)
    {
        if(strstr(s,prev)==s){
            strcpy(&replace[i],new);
            i+=nLength;
            s+=pLength;
        }
        else{
            replace[i++] = *s++;
        }
        
    }
    
    replace[i] = '\0';
    return replace;
}





int main()
{
    FILE *ptr1=NULL;
    FILE *ptr2=NULL;
    char s[202];
    char temp[30];
    char *pointer;

    ptr1 = fopen("input.txt","r");//read
    ptr2 = fopen("output.txt","a");//append


    if(ptr1==NULL) printf("File doesn't exist.\n");


    fgets(s, 200, ptr1);

    printf("Enter your name: ");
    scanf(" %[^\n]s",temp);
    pointer = Update(s,"{{name}}",temp);
    // printf("%s\n",pointer);

    printf("Enter your ID: ");
    scanf(" %[^\n]s",temp);
    pointer = Update(pointer,"{{id}}",temp);
    // printf("%s\n",pointer);


    printf("Enter your Department: ");
    scanf(" %[^\n]s",temp);
    pointer = Update(pointer,"{{Department}}",temp);
    // printf("%s\n",pointer);
    
    printf("%s\n",pointer);

    fprintf(ptr2,"%s",pointer);


    fclose(ptr1);
    fclose(ptr2);
    free(pointer);
    

    return 0;
}

Learn 6 Sorting Algorithm in ONE CODE!

noreply@blogger.com (Mahmudul Hasan) — Thu, 03 Dec 2020 09:03:00 +0000

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<limits.h>
#include<stdbool.h>

int n;
int* input;

void swap(int* a, int* b)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}
//Taking User input
void userinput()
{
    printf("Enter array size:");
    scanf("%d\n",&n);
    input = (int*)malloc(n*sizeof(int));
    int i;
    for(i=0;i<n;i++)
    {
        scanf("%d",&input[i]);
    }
}
//Printing result
void result()
{
    int i;
    for(i=0;i<n;i++)
    {
        printf("%d ",input[i]);
    }
    free(input);
    printf("\n");
}
//1. Insertion Counting
void insertion()
{    
    int i,j,key;
    for(i=1;i<n;i++)
    {
        key=input[i];
        j=i-1;
        while(j>=0 && input[j]>key)
        {
            input[j+1]=input[j];
            j--;
        }
        input[j+1]=key;
    }
}
//2. Bubble Sorting
void bubble()
{
    int i,j;

    for(int i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if(input[j]>input[j+1])
            {
                swap( &input[j], &input[j+1] );
            }
        }
    }
}
//3. Selection sort
void selection()
{
    int i,j;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(input[i]>input[j])
            {
                swap( &input[i], &input[j]);
            }
        }
    }    
}
//4. Counting Sorting
void counting()
{    
    int i,j;
    int mx= INT_MIN;
    int mn= INT_MAX;

    for(i=0;i<n;i++)
    {
        if(input[i]>mx) mx=input[i];
        if(input[i]<mn) mn=input[i];
    }
    int range=mx-mn+1;
    int* aux;
    aux=(int*)calloc(range,sizeof(int));

    for(i=0;i<n;i++)
    {
        aux[input[i]-mn]+=1;
    }
    for(i=1;i<range;i++)
    {
        aux[i]+=aux[i-1];
    }
    int* output;
    output=(int*)calloc(n,sizeof(int));
    for(i=n-1;i>=0;i--)
    {
        output[aux[input[i]-mn]-1]=input[i];
        aux[input[i]-mn]-=1;
    }
    free(aux);
    for(i=0;i<n;i++)
    {
        input[i]=output[i];
    }
    free(output);
}
//using for radix sort
void cntSort(int e)
{
    int* aux;
    int i,j;
    aux = (int*)calloc(10,sizeof(int));

    for(i=0;i<n;i++)
    {
        aux[ (input[i]/e) % 10]+=1;
    }
    for(i=1;i<10;i++)
    {
        aux[i]+=aux[i-1];
    }
    int* output;
    output = (int*)calloc(n,sizeof(int));
    for(i=n-1;i>=0;i--)
    {
        output[ aux[(input[i]/e)%10]-1] = input[i];
        aux[(input[i]/e)%10]--;
    }
    for(i=0;i<n;i++)
    {
        input[i]=output[i];
    }
    free(output);
    free(aux);
}
//5. Radix Sort
void radix()
{  
    int i,j;
    int mx= INT_MIN;

    for(i=0;i<n;i++)
    {
        if(input[i]>mx) mx=input[i];
    }
    int e;
    for(e=1;mx/e>0;e*=10)
    {
        cntSort(e);
    }
}
// 6. Bucket sort
void bucket()
{  
    int i,j,k,num;
    printf("Enter the Array size:");
    scanf("%d",&num);
    
    double* arr=(double*)malloc(num*sizeof(double));

    for(i=0;i<num;i++)
    {
        scanf("%lf",&arr[i]);
    }

    double b[30][100];
    int cnt[30];
    memset(cnt,0,sizeof(int));

    for(i=0;i<num;i++)
    {
        int bi=num*arr[i];
        
        b[bi][cnt[bi]++]=arr[i];
    }

    for(i=0;i<30;i++)
    {
        for(k=1;k<cnt[i];k++)
        {
            double key= b[i][k];
            j=k-1;
            while(j>=0 && b[i][j]>key)
            {
                b[i][j+1]=b[i][j];
                j--;
            }
            b[i][j+1]=key;
        }
    }
    int index=0;

    for(i=0;i<30;i++)
    {
        for(j=0;j<cnt[i];j++)
        {
            arr[index++]=b[i][j];
        }
    }

    for(i=0;i<num;i++)
    {
        printf("%0.3lf ",arr[i]);
    }
    free(arr);
    printf("\n");
}


int main()
{
    int a;
    printf("Enter your Choice:\n1. Insertion Sort\n2. Bubble Sort\n3. Selection Sort\n4. Counting Sort\n5. Radix Sort\n6. Bucket Sort\n***Enter 0 to exit.\n");
    while(1)
    {
        scanf("%d",&a);
        switch(a)
        {
            case 1:
            {
                printf("Insertion sort\n");
                userinput();
                insertion();
                result();
                break;
            }
            case 2:
            {
                printf("Bubble sort\n");
                userinput();
                bubble();
                result();
                break;
            }
            case 3:
            {
                printf("Selection sort\n");
                userinput();
                selection();
                result();
                break;
            }
            case 4:
            {
                printf("Counting sort\n");
                userinput();
                counting();
                result();
                break;
            }
            case 5:
            {
                printf("Radix sort\n");
                userinput();
                radix();
                result();
                break;
            }
            case 6:
            {
                printf("Bucket sort\n");
                bucket();
                break;
            }
            
            case 0:
            {
                //printf("Program Terminated.\n");
                break;
            }
            default:
            {
                //printf("Program Terminated.\n");
                break;
            }

        }
        if(a==0)
        {
            printf("Program Terminated.\n");
            break;
        }
               
    }

    return 0;
}

HTML Parser

noreply@blogger.com (Mahmudul Hasan) — Sat, 28 Nov 2020 05:05:00 +0000

Sample input:

Sample output:

 #include<stdio.h>
#include<string.h>

void parser(char *string)
{
    int in=0;
    int index=0,i;

    for(i=0;i<strlen(string);i++)
    {
        if(string[i]=='<')
        {
            in=0;
            continue;
        }
        else if(string[i]=='>')
        {
            in=1;
            continue;
        }

        if(in)
        {
            string[index]=string[i];
            index++;
        }
    }
    string[index]='\0';
    while(string[0]==' ')
    {
        for(i=0;i<strlen(string);i++)
        {
            string[i]=string[i+1];
        }
    }
    while(string[strlen(string)-1]==' ')
    {
        string[strlen(string)-1]='\0';
    }

}


int main()
{
    char string[50];

    scanf("%[^\n]s",string);

   // printf("%s\n",string);

    parser(string);

    printf("~~%s~~\n",string);

    return 0;
}

Implementation of Double-Dabble Method in C

noreply@blogger.com (Mahmudul Hasan) — Thu, 26 Nov 2020 09:40:00 +0000

C code to convert a binary string into decimal:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main()
{
 
    char bin[65];

    

    scanf("%s",bin);
    int len=strlen(bin);
    long long dec=bin[0]-'0';


    for(int i=1;i<len;i++)
    {
        dec=dec*2+(bin[i]-'0');
    }

    printf("%lld\n",dec);

    return 0;
}

Modular multiplicative inverse

noreply@blogger.com (Mahmudul Hasan) — Mon, 23 Nov 2020 10:05:00 +0000

1. When a and m are co-PRIME:

#include<bits/stdc++.h>
using namespace std;
int extdGcd(int a,int b, int* x,int* y)
{
    if(a==0)
    {
        *x=0, *y=1;
        return b;
    }

    int x1,y1;

    int gcd=extdGcd(b%a,a,&x1,&y1);

    *x=y1-(b/a)*x1;
    *y=x1;

    return gcd;

}




void InverseMod(int a,int m)
{
    int x,y;

    int g= extdGcd(a,m,&x,&y);

    if(g!=1)
    {
        printf("Modular Multiplicative Inverse doesn't exist.\n");
    } 
    else
    {
        int inv=(x%m+m)%m;
        printf("Modular Multiplicative Inverse is: %d\n",inv);
    }
    
}



int main()
{
    int a,m;
    scanf("%d %d",&a,&m);
    InverseMod(a,m);

    return 0;
}

2. When m is PRIME(Using FLT):

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

int gcd(int n,int m)
{
    if(n==0) return m;

    return gcd(m%n,n);
}

int bigMod(int x,int y,int m)
{
    if(y==0) return 1;
    
    if(y&1)
    {
        int p1=x%m;
        int p2=bigMod(x,y-1,m);

        return (p1*p2)%m;
    }
    else
    {
        int h1=bigMod(x,y/2,m);
        return (h1*h1)%m;
    }
    

}



void InverseMod(int n,int m)
{

  int g= gcd(n,m);
  if(g!=1)
    cout<<"Inverse doesn't exist.\n";

  else
  {
      cout<<"Modular Multiplicative Inverse is:"<<bigMod(n,m-2,m)<<endl;
  }

}







int main()
{
    int t;

    cin>>t;

    while(t--)
    {
        int n,m;
        cin>>n>>m;

        InverseMod(n,m);
    }

    return 0;
}

DP- KnapSacks HackerEarth

noreply@blogger.com (Mahmudul Hasan) — Mon, 16 Nov 2020 12:31:00 +0000

KnapSacks HackerEarth

#include<bits/stdc++.h>

using namespace std;

#define file() freopen("in.txt","r",stdin)

#define IO ios_base::sync_with_stdio(false),cin.tie(0)

#define ll long long
int n;
int w;
int val[1005];
int wt[1005];
int sum=0;


    int result()
    {
        for(int i=0;i<n;i++)
        {
            sum+=val[i];
        }

        vector<ll>dp(sum+1,INT_MAX);

        dp[0]=0;

        for(int i=0;i<n;i++)
        {
            for(int j=sum;j>=0;j--)
            {
                if(j>=val[i])
                {
                    dp[j] = min(dp[j],wt[i]+dp[j-val[i]]);
                }

            }
        }

        for(int i=sum;;i--)
        {
            if(dp[i]<=w) return i;
        }




    }





    int main()
    {


       // file();

        scanf("%d%d",&n,&w);

        for(int i=0;i<n;i++)
        {
            scanf("%d",&val[i]);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&wt[i]);
        }


        cout<<result()<<endl;

    return 0;

    }

Finding String Length Without Library Function

noreply@blogger.com (Mahmudul Hasan) — Thu, 12 Nov 2020 13:48:00 +0000

 #include<bits/stdc++.h

using namespace std;

int Length(string a)
{
    int cnt=0,i=0;
    while(a[i++]!='\0')
    {
        cnt++;
    }
    return cnt;
}

int main()
{

    string a;
    cin>>a;

    cout<<Length(a)<<endl;

    
    return 0;
}

Converting DECIMAL to BINARY

noreply@blogger.com (Mahmudul Hasan) — Wed, 11 Nov 2020 15:32:00 +0000

 #include<bits/stdc++.h>

using namespace std;

#define file() freopen("in.txt","r",stdin)

#define IO ios_base::sync_with_stdio(false),cin.tie(0)



int main()
{
    int n;
    cin>>n;
  
  
    for(int c=31;c>=0;c--)
    {
        int k=n>>c;
        if(k&1) {
            cout<<1;
        }
        else cout<<0;
    }
    cout<<endl;

    return 0;
}

UVa 10487 - Closest Sums

noreply@blogger.com (Mahmudul Hasan) — Fri, 02 Oct 2020 16:38:00 +0000

10487 - Closest Sums

#include<bits/stdc++.h>
using namespace std;
long long arr[1010];
long long sum[1000009];

long long closestSum1(long long q, long long c)
{
    long long l=-1,r=c,m;

    while(r>l+1)
    {
        m=(l+r)/2;
        if(sum[m]<=q) l=m;
        else r=m;
    }
    return l;
}




int main()
{
    
    long long n,i,k,l,m,z=1,query,j,q;

    while(scanf("%lld",&n)&&n)
    {

        for(i=0;i<n;i++)
        {
            scanf("%lld",&arr[i]);
        } 
        long long c=0;
        for(i=0;i<n-1;i++)
        {
            for(j=i+1;j<n;j++)
            {
                sum[c]=arr[i]+arr[j];
                c++;
            }
        }
        sort(sum,sum+c);
        scanf("%lld",&query);
        printf("Case %lld:\n",z);
        for(j=1;j<=query;j++)
        {
            scanf("%lld",&q);
            if(q<=sum[0]) printf("Closest sum to %lld is %lld.\n",q,sum[0]);
            else if(q>=sum[c-1])   printf("Closest sum to %lld is %lld.\n",q,sum[c-1]);
            else 
            {
                long long x=closestSum1(q,c);
                if(abs(q-sum[x])<abs(sum[x+1]-q))  printf("Closest sum to %lld is %lld.\n",q,sum[x]);
                else  printf("Closest sum to %lld is %lld.\n",q,sum[x+1]);
            }
            
        }
        z++;


    }


    return 0;
}

10703 - Free spots

noreply@blogger.com (Mahmudul Hasan) — Thu, 01 Oct 2020 11:58:00 +0000

10703 - Free spots

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

bool arr[510][510];

void reset()
{
  for(int k=0;k<=508;k++) 
    memset(arr[k],false,sizeof(arr[k]));
}

int mx(int a, int b)
{
  return (a>b)? a:b;
}
int mn(int a, int b)
{
  return (a<b)? a:b;
}

int main()
{
 //freopen("in.txt","r",stdin);
  int W,H,N;

  while(scanf("%d%d%d",&W,&H,&N)!=EOF)
  {
    
   if(W==0 && H==0 && N==0) break;
   reset();
   int i,j,x1,y1,x2,y2,l,m,points=0;

   for(i=1;i<=N;i++)
   {
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    int X1,Y1,X2,Y2;
    X1=mn(x1,x2);
    Y1=mn(y1,y2);
    X2=mx(x1,x2);
    Y2=mx(y1,y2);
   
    for(j=X1;j<=X2;j++)
    {
      for(l=Y1;l<=Y2;l++)
      {
        arr[j][l]=true;
      }
    }
    
   }
   for(i=1;i<=W;i++)
   {
     for(j=1;j<=H;j++)
     {
       if(arr[i][j]==false) points++;
     }
   }
      if ( points == 0 ) printf ("There is no empty spots.\n");
      else if ( points == 1 ) printf ("There is one empty spot.\n");
      else printf ("There are %d empty spots.\n", points);

  }
 

  return 0;
}

Selection Sort

noreply@blogger.com (Mahmudul Hasan) — Mon, 21 Sep 2020 01:10:00 +0000

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

int main()
{
    ios_base :: sync_with_stdio(0),cin.tie(0);
   // freopen("in.txt","r",stdin);

   int x;
   int count[202];
   int n;
   cin>>n;
   int key;
   for(int i=0;i<n;i++)
   {
      cin>>count[i];
   }
   for(int i=0;i<n-1;i++)
   {
      
     for(int j=i+1;j<n;j++)
     {
         if(count[i]>count[j])
         {
             int temp=count[i];
             count[i]=count[j];
             count[j]=temp;
         }
     }

   }
   for(int i=0;i<n;i++)
   {
    cout<<count[i]<<" ";
   }
   cout<<endl;

    return 0;
}

Bubble Sort- C++

noreply@blogger.com (Mahmudul Hasan) — Sun, 13 Sep 2020 17:47:00 +0000

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

#define ll long long
#define IO ios_base::sync_with_stdio(0),cin.tie(0)

void bubble(int arr[],int n)
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                int temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
            }
        }
    }


}



int main()
{
    IO;

    int arr[]={5,1,4,3,2,0};

    int n=sizeof(arr)/sizeof(arr[0]);

    bubble(arr,n);

    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;

    return 0;
}

Insertion Sort -C++

noreply@blogger.com (Mahmudul Hasan) — Tue, 01 Sep 2020 13:56:00 +0000

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

int main()
{
    ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
   // freopen("in.txt","r",stdin);
    int ara[] = {5,4,3,2,1 }; 
    int n=sizeof(ara)/sizeof(ara[0]);

    int i,j,k;

    for(i=1;i<n;i++)
    {
        j=i-1;
       int key=ara[i];

        while(j>=0 && ara[j]>key)
        {
            ara[j+1]=ara[j];
            j--;
        }
        ara[j+1]=key;


    }
for(i=0;i<n;i++)
{
    cout<<ara[i]<<" ";   
}
cout<<endl;

    return 0;
}

Sort -C

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 20:16:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

// freopen("in.txt","r",stdin);

int ara[100],n,i,j;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&ara[i]);

}

for(i=0;i<n;i++)

{

for(j=i+1;j<n;j++)

{

if(ara[i]>ara[j])

{

int temp=ara[j];

ara[j]=ara[i];

ara[i]=temp;

}

for(i=0;i<n;i++)

{

printf("%d ",ara[i]);

}

printf("\n");

return 0;

}

Sum of two matrices-C

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 20:01:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

// freopen("in.txt","r",stdin);

int mat1[3][3],mat2[3][3];

int i,j;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

scanf("%d",&mat1[i][j]);

}

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

scanf("%d",&mat2[i][j]);

}

int mat[3][3];

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

mat[i][j]=mat1[i][j]+mat2[i][j];

}

printf("\n");

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

printf("%d ",mat[i][j]);

}

printf("\n");

}

return 0;

}

Printing transpose of a MATRIX-C/C++

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 19:56:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

// freopen("in.txt","r",stdin);

int mat[3][3];

int i,j;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

scanf("%d",&mat[i][j]);

}

int temp;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

if(j-i>=0)

{

temp=mat[i][j];

mat[i][j]=mat[j][i];

mat[j][i]=temp;

}

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

printf("%d ",mat[i][j]);

}

printf("\n");

}

return 0;

}

printing 3x3 set-C/C++

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 19:42:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

// freopen("in.txt","r",stdin);

int mat[3][3];

int i,j;

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

scanf("%d",&mat[i][j]);

}

for(i=0;i<3;i++)

{

for(j=0;j<3;j++)

{

printf("%d ",mat[i][j]);

}

printf("\n");

}

return 0;

}

Counting Numbers 2 -C/C++

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 19:35:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

// freopen("in.txt","r",stdin);

int ara[101],n,i,j;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&ara[i]);

}

int nums[101],num[101];

for(i=0;i<101;i++)

{

nums[i]=0;

num[i]=0;

}

int cnt=0;

for(i=0;i<n;i++)

{

nums[ara[i]]++;

num[ara[i]]=ara[i];

}

for(i=0;i<101;i++)

{

if(nums[i]!=0)

{

printf("%d %d\n",num[i],nums[i]);

}

puts("");

return 0;

}

Printing Unique Number-C/C++

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 19:06:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

// freopen("in.txt","r",stdin);

int ara[101],n,i,j;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d",&ara[i]);

}

printf("%d ",ara[0]);

for(i=1;i<n;i++)

{

int cnt=0;

for(j=0;j<i;j++)

{

if(ara[i]==ara[j])

{

cnt++;

}

if(cnt==0)

{

printf("%d ",ara[i]);

}

puts("");

return 0;

}

snake-C++

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 18:10:00 +0000

    #include<bits/stdc++.h>
    #include<conio.h>
    #include<windows.h>

    using namespace std;


    bool over;

    int x,y,FrX,FrY,score=0,i,j;
    char m;
    const int height=20;
    const int width=40;
    enum direction {STOP=0,RIGHT,LEFT,UP,DOWN};
    direction dir;

    void setup()
    {
        over=false;
        dir=STOP;
        y=height/2;
        x=width/2;
        FrX=rand()%width;
        FrY=rand()%height;
        score=0;

    }


    void draw()
    {

        system("cls");
        for(j=0;j<=width+2;j++){
        cout<<"#";
        }
        cout<<endl;
        for(i=0;i<=height;i++){
            for(j=0;j<=width;j++){

            if(j==0) cout<<"#";

            if(i==y && j==x) cout<<"O";

            else if(i==FrY && j==FrX) cout<<"F";

            else cout<<" ";

            if(j==width) cout<<"#";
            }
            cout<<endl;
    }

        for(j=0;j<=width+2;j++){
            cout<<"#";
        }
        cout<<endl;
        cout<<"SCORE: "<<score<<endl;
    }



    void input(){

    if(_kbhit()){
        switch(_getch()){
                case 'a': dir=LEFT; break;
                case 'l': dir=RIGHT; break;
                case 'u': dir=UP; break;
                case 'd': dir=DOWN; break;
                case 'x': over=true; break;
            }
        }
    }


    void logic(){
        switch(dir)
        {
        case LEFT: x--; break;
        case RIGHT: x++; break;
        case UP: y--; break;
        case DOWN: y++; break;
        default: break;
        }

        if(x>width||x<0||y>height || y<0) over=true;

        if(x==FrX && y==FrY){
            score+=10;
            FrX=rand()%width;
            FrY=rand()%height;
        }

    }


    int main(){
        ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

        setup();

        while(!over){
        draw();
        input();
        logic();
        Sleep(10);
        }


        return 0;

    }

Finding Max and Min of an Array -C

noreply@blogger.com (Mahmudul Hasan) — Mon, 24 Aug 2020 16:48:00 +0000

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);

//freopen("input.txt","r",stdin);

int ara[101],n;

scanf("%d",&n);

int i,j;

for(i=0;i<n;i++)

{

scanf("%d",&ara[i]);

}

int max=ara[0],min=ara[0];

for(i=0;i<n;i++)

{

if(max<ara[i]) max=ara[i];

if(min>ara[i]) min=ara[i];

}

printf("%d %d\n",max,min);

return 0;

}