DOUBLY LINKED LIST

Source code in C:
/********************************************************************************/
// Doubly LinkList
#include<stdio.h>
#include<stdlib.h>

struct Node
{
    int data;
    struct Node*next,*prev;
};

typedef struct Node Node;

Node*sort2(Node*,Node**);
Node*sort(Node*start,Node**);
void reversePrinting(Node*);
void insertAfter(Node*,Node**,int,int);
Node* insertBefore(Node*,Node**,int,int);
void printList(Node*);
Node*insertLast(Node*,Node**,Node*);
Node*createNode(int);
int search(Node*,int);
Node*Delete(Node*,Node**,int);
Node*deleteLast(Node*,Node**);

int main()
{
    int temp,ch,num;
    Node *newNode,*start,*last;
    start=last=NULL;
    while(1)
    {
        printf("\n_________________menu__________________\n");
        printf("1. insert at the end of list...\n");
        printf("2. print the list...\n");
        printf("3. search a speific item...\n");
        printf("4. insert after a specific node...\n");
        printf("5. insert a node before a specific node...\n");
        printf("6. delete a specific node...\n");
        printf("7. delete a last node...\n");
        printf("8. reverse printing of the list\n");
        printf("9. sort the link list...\n");
        printf("10. sort the link list(another method)...\n");
        printf("11. exit...\n");

        printf("\nenter your choice : ");
        scanf("%d",&ch);

        switch(ch)
        {
            case 1:
                printf("enter the data part of the node that you want to insert :\n");
                scanf("%d",&temp);
                newNode=createNode(temp);
                start=insertLast(start,&last,newNode);
                break;
            case 2:
                printList(start);
                break;
            case 3:
                printf("enter the data that you want to search : ");
                scanf("%d",&temp);
                if(search(start,temp))
                    printf("the number you entered was in the list");
                else
                    printf("the number you entered was not in the list");
                break;
            case 4:
                printf("enter the data of the node after which you want to insert new node : ");
                scanf("%d",&temp);
                printf("enter the data part of the node that you want to insert : ");
                scanf("%d",&num);
                insertAfter(start,&last,temp,num);
                break;
            case 5:
                printf("enter the data of the node before which you want to insert new node : ");
                scanf("%d",&temp);
                printf("enter the data part of the node that you want to insert : ");
                scanf("%d",&num);
                start=insertBefore(start,&last,temp,num);
                break;
            case 6:
                printf("enter the data part of the node that you want to delete : ");
                scanf("%d",&temp);
                start=Delete(start,&last,temp);
                break;
            case 7:
                if(last==NULL)
                {
                    printf("the list is empty...you can't delete any node...");
                    break;
                }
                start=deleteLast(start,&last);
                break;
            case 8:
                reversePrinting(last);
                break;
            case 9:
                start=sort(start,&last);
                break;
            case 10:
                start=sort2(start,&last);
                break;
            case 11:
                exit(1);
            default:
                printf("you have entered a wrong choice...enter a valid choice");
        }
    }
}

Node* createNode(int data)
{
    Node*newNode;
    newNode=(Node*)malloc(sizeof(Node));
    newNode->data=data;
    newNode->next=newNode->prev=NULL;
    return newNode;
}

Node*insertLast(Node*start,Node**p2last,Node*newNode)
{
    if(*p2last==NULL)
    {
        *p2last=newNode;
        return newNode;
    }
    (*p2last)->next=newNode;
    newNode->prev=*p2last;
    *p2last=newNode;
    return start;
}

void printList(Node*start)
{
    printf("your list is as follows : \n");
    while(start)
    {
        printf("%d\t",start->data);
        start=start->next;
    }
}

int search(Node*start,int data)
{
    while(start)
    {
        if(start->data==data)
            return 1;
        start=start->next;
    }
    return 0;
}

void insertAfter(Node*start,Node**p2last,int data,int num)
{
    Node*newNode,*tmp;
    newNode=createNode(num);
    if(*p2last==NULL)
        printf("the list is empty...");
    tmp=start;
    while(tmp)
    {
        if(tmp->data==data)
            break;
        tmp=tmp->next;
    }
    if(!tmp)
        printf("the number you enter was not in the list\n");
    else
    {
        newNode->next=tmp->next;
        tmp->next=newNode;
        newNode->prev=tmp;
        if(tmp==*p2last)
        {
            newNode->prev=*p2last;
            *p2last=newNode;
        }
    }
}

Node*insertBefore(Node*start,Node**p2last,int data,int num)
{
    Node*newNode,*tmp;
    newNode=createNode(num);
    if(*p2last==NULL)
    {
        printf("the list is empty...");
        return start;
    }
    if(start->data==data)
    {
        start->prev=newNode;
        newNode->next=start;
        return newNode;
    }
    tmp=start;
    while(tmp)
    {
        if(tmp->data==data)
            break;
        tmp=tmp->next;
    }
    if(!tmp)
        printf("the number you enter was not in the list\n");
    else
    {
        newNode->next=tmp;
        newNode->prev=tmp->prev;
        tmp->prev=newNode;
        newNode->prev->next=newNode;
        if(tmp==*p2last)
        {
            newNode->next=*p2last;
            (*p2last)->prev=newNode;
        }
    }
    return start;   
}

Node*Delete(Node*start,Node**p2last,int data)
{
    Node*ptr;
    for(ptr=start;ptr;ptr=ptr->next)
    {
        if(ptr->data==data)
            break;
    }
    if(!ptr)
    {
        printf("the number you entered was not found in the list...!!!");
        return start;
    }
    if(ptr==start)
    {
        if(start->next==NULL)
        {
            *p2last=NULL;
            return NULL;
        }
        start->next->prev=NULL;
        return start->next;
    }
    if((*p2last)->data != data)
    {
        ptr->prev->next=ptr->next;
        ptr->next->prev=ptr->prev;
        return start;
    }
    (*p2last)->prev->next=NULL;
    *p2last=(*p2last)->prev;
    return start;
 }

Node*deleteLast(Node*start,Node**p2last)
{
    return Delete(start,p2last,(*p2last)->data);
}

void reversePrinting(Node*last)
{
    Node*ptr;
    printf("the reverse printing of the list is : \n");
    for(ptr=last;ptr;ptr=ptr->prev)
        printf("%d\t",ptr->data);
}

Node*sort(Node*start,Node**p2last)
{
    Node*ptr,*newNode,*tmp,*start1,*last1;
    start1=last1=NULL;
    while(start!=NULL)
    {
        tmp=ptr=start;
        while(ptr)
        {
            if(tmp->data > ptr->data)
                tmp=ptr;
            ptr=ptr->next;
        }
        newNode=createNode(tmp->data);
        start1=insertLast(start1,&last1,newNode);
        start=Delete(start,p2last,tmp->data);
    }
    *p2last=last1;
    return start1;
}

Node*sort2(Node*start,Node**p2last)
{
    int *arr,count=0,i,tmp,j;
    Node*ptr,*start1,*last1,*newNode;
    ptr=start;
    start1=last1=NULL;
    while(ptr)
    {
        count++;
        ptr=ptr->next;
    }

    arr=(int*)malloc(sizeof(int)*count);
   
    ptr=start;
    for(i=0;i<count;i++)
    {
        arr[i]=ptr->data;   
        ptr=ptr->next;
    }
   
    /* sorting the array bubble */
    for(i=1;i<count;i++)
        for(j=0;j<count-i;j++)
            if(arr[j]>arr[j+1])
            {
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
   
    for(i=0;i<count;i++)
        start1=insertLast(start1,&last1,createNode(arr[i]));
    *p2last=last1;
    return start1;
}
/****************************************************************************/

CIRCULARLY LINKED LIST

Source code in C:
/****************************************************************************/
// Circular Link List
#include<stdio.h>
#include<stdlib.h>

struct Node
{
    int data;
    struct Node*next;
};

typedef struct Node Node;

Node*createNode(int);
Node*insertLast(Node*,int);
void printList(Node*);
int search(Node*,int);
Node*insertAfter(Node*,int,int);
Node*insertBefore(Node*,int,int);
Node*Delete(Node*,int);
Node*deleteLast(Node*);
Node*reverseList(Node*);
Node*sort(Node*);
int countNodes(Node*);

int main()
{
    int ch,tmp,n;
    Node*start;
    start=NULL;

    while(1)
    {
        printf("\n_________________menu__________________\n");
        printf("1. insert at the end of list...\n");
        printf("2. print the list...\n");
        printf("3. search a speific item...\n");
        printf("4. insert after a specific node...\n");
        printf("5. insert a node before a specific node...\n");
        printf("6. delete a specific node...\n");
        printf("7. delete a last node...\n");
        printf("8. reverse the list...\n");
        printf("9. sort the link list...\n");
        printf("10. count the total number of node in the list...\n");
        printf("11. exit...\n");

        printf("\nenter your choice : ");
        scanf("%d",&ch);

        switch(ch)
        {
            case 1:
                printf("enter the data part of the node that you want to insert... : ");
                scanf("%d",&tmp);
                start=insertLast(start,tmp);
                break;
            case 2:
                printList(start);
                break;
            case 3:
                printf("enter the data item that you want to search : ");
                scanf("%d",&tmp);
                if(search(start,tmp))
                    printf("the data you entered was found in the list...");
                else
                    printf("the data you entered was not found in the list...");
                break;
            case 4:
                printf("enter the data part of the node after which you want to insert new node");
                scanf("%d",&n);
                printf("enter the data part of the node that you want to insert : ");
                scanf("%d",&tmp);
                start=insertAfter(start,n,tmp);
                break;
            case 5:
                printf("enter the data part of the node before which you want to insert new node");
                scanf("%d",&n);
                printf("enter the data part of the node that you want to insert : ");
                scanf("%d",&tmp);
                start=insertBefore(start,n,tmp);
                break;
            case 6:
                printf("enter the data part of the node that you want to delete...");
                scanf("%d",&tmp);
                start=Delete(start,tmp);
                break;
            case 7:
                start=deleteLast(start);
                break;
            case 8:
                start=reverseList(start);
                break;
            case 9:
                start=sort(start);
                break;
            case 10:
                printf("the total number of nodes are : %d",countNodes(start));
                break;
            case 11:
                exit(1);
            default:
                printf("you have entered a wrong choice !!!!");
        }
    }
    return 0;
}

Node*createNode(int data)
{
    Node*newNode;
    newNode=(Node*)malloc(sizeof(Node));
    newNode->data=data;
    newNode->next=NULL;
    return newNode;
}

Node*insertLast(Node*start,int data)
{
    Node*newNode,*ptr;
    newNode=createNode(data);
    if(start==NULL)
    {
        newNode->next=newNode;
        return newNode;
    }
    for(ptr=start;ptr->next!=start;ptr=ptr->next);
    newNode->next=start;
    ptr->next=newNode;
    return start;
}

void printList(Node*start)
{
    Node*ptr;
    ptr=start;
    if(start)
        do
        {
            printf("%d\t",ptr->data);
            ptr=ptr->next;
        }while(ptr!=start);
}

int search(Node*start,int data)
{
    Node*ptr=start;
    if(!start)
        return 0;
    do
    {
        if(ptr->data==data)
            return 1;
        ptr=ptr->next;
    }while(ptr!=start);
    return 0;
}

Node*insertAfter(Node*start,int data,int tmp)
{
    Node *ptr,*newNode;
    newNode=createNode(tmp);
    ptr=start;
    if(!start)
    {
        printf("the list is empty...");
        return start;
    }
   
    do
    {
        if(ptr->data==data)
            break;
        ptr=ptr->next;
    }while(ptr->next!=start);

    if(ptr->next==start && ptr->data==data)
    {
        ptr->next=newNode;
        newNode->next=start;
        return start;
    }
    if(ptr->next==start && ptr==start)
    {
        ptr->next=newNode;
        newNode->next=start;
        return start;
    }
    newNode->next=ptr->next;
    ptr->next=newNode;
    return start;
}

Node*insertBefore(Node*start,int data,int tmp)
{
    Node *ptr,*newNode,*prev,*temp;
    newNode=createNode(tmp);
    ptr=start;
    if(!start)
    {
        printf("the list is empty");
        return start;
    }
    do
    {
        if(ptr->data==data)
            break;
        prev=ptr;
        ptr=ptr->next;
    }while(ptr->next!=start);
   
    if(ptr->next==start)
    {
        if(ptr->data==data)
        {
            prev->next=newNode;
            newNode->next=ptr;
            return start;
        }
        printf("number you entered is not in the list");
        return start;
    }

    if(ptr->next==start && ptr==start) /*this is the condition for only one node in the list*/
    {
        newNode->next=ptr;
        ptr->next=newNode;
        return newNode;
    }
   
    if(ptr==start && ptr->data==data)
    {
        newNode->next=start;
        temp=start;
        for(temp=start;temp->next!=start;temp=temp->next);
        temp->next=newNode;
        return newNode;
    }
    newNode->next=ptr;
    prev->next=newNode;
    return start;
}

Node*Delete(Node*start,int data)
{
    Node*ptr,*prev,*tmp;
    prev=NULL;
    ptr=start;
    if(!start)
    {
        printf("the list is empty...");
        return start;
    }
    for(ptr=start;ptr->next!=start;prev=ptr,ptr=ptr->next)
    {
        if(ptr->data==data)
            break;
    }
    if(ptr->next==start)
    {
        if(ptr->data==data && ptr==start)
        {
            return NULL;
        }

        if(ptr->data==data)
        {
            prev->next=ptr->next;
            return start;
        }
        printf("the data value you entered was not found in the list...");
        return start;
    }
    if(prev==NULL)
    {
        for(tmp=start;tmp->next!=start;tmp=tmp->next);
        tmp->next=start->next;
        return start->next;
    }
    prev->next=ptr->next;
    return start;   
}

Node*deleteLast(Node*start)
{
    Node*tmp;
    for(tmp=start;tmp->next!=start;tmp=tmp->next);
    return Delete(start,tmp->data);   
}

Node*reverseList(Node*start)
{
    Node*tmp,*start1;
    start1=NULL;
    if(!start)
    {
        printf("the list is empty...");
        return start;
    }
    while(start)
    {
        for(tmp=start;tmp->next!=start;tmp=tmp->next);
        start1=insertLast(start1,tmp->data);
        start=deleteLast(start);   
    }
    return start1;
}

Node*sort(Node*start)
{
    Node*tmp,*ptr,*start1;
    start1=NULL;
    while(start)
    {
        for(tmp=start,ptr=start;tmp->next!=start;tmp=tmp->next)
        {
            if(ptr->data > tmp->data)
                ptr=tmp;
        }
        /*now ptr contains the address of that node that has minimum data part */
        start1=insertLast(start1,ptr->data);
        start=Delete(start,ptr->data);
    }
    return start1;
}

int countNodes(Node*start)
{
    Node*ptr;
    int counter=0;
    if(!start)
        return 0;
    for(ptr=start;ptr->next!=start;ptr=ptr->next)
        counter++;
    return counter+1;
}
/****************************************************************************/

SINGLY LINKED LIST

Source code in C :
/*************************************************************************/
//Single LinkList
#include<stdio.h>
#include<stdlib.h>

struct Node
{
    int data;
    struct Node*next;
};

typedef struct Node Node;
Node*sort2(Node*,Node**);
Node*sort(Node*start,Node**);
Node*reverseList(Node*,Node**);
void insertAfter(Node*,Node**,int,int);
Node* insertBefore(Node*,int,int);
void printList(Node*);
Node*insertLast(Node*,Node**,Node*);
Node*createNode(int);
int search(Node*,int);
Node*Delete(Node*,Node**,int);
Node*deleteLast(Node*,Node**);

int main()
{
    int temp,ch,num;
    Node *newNode,*start,*last;
    start=last=NULL;
    while(1)
    {
        printf("\n_________________menu__________________\n");
        printf("1. insert at the end of list...\n");
        printf("2. print the list...\n");
        printf("3. search a speific item...\n");
        printf("4. insert after a specific node...\n");
        printf("5. insert a node before a specific node...\n");
        printf("6. delete a specific node...\n");
        printf("7. delete a last node...\n");
        printf("8. reverse the link list...\n");
        printf("9. sort the link list...\n");
        printf("10. sort the link list(another method)...\n");
        printf("11. exit...\n");

        printf("\nenter your choice : ");
        scanf("%d",&ch);

        switch(ch)
        {
            case 1:
                printf("enter the data part of the node that you want to insert :\n");
                scanf("%d",&temp);
                newNode=createNode(temp);
                start=insertLast(start,&last,newNode);
                break;
            case 2:
                printList(start);
                break;
            case 3:
                printf("enter the data that you want to search : ");
                scanf("%d",&temp);
                if(search(start,temp))
                    printf("the number you entered was in the list");
                else
                    printf("the number you entered was not in the list");
                break;
            case 4:
                printf("enter the data of the node after which you want to insert new node : ");
                scanf("%d",&temp);
                printf("enter the data part of the node that you want to insert : ");
                scanf("%d",&num);
                insertAfter(start,&last,temp,num);
                break;
            case 5:
                printf("enter the data of the node before which you want to insert new node : ");
                scanf("%d",&temp);
                printf("enter the data part of the node that you want to insert : ");
                scanf("%d",&num);
                start=insertBefore(start,temp,num);
                break;
            case 6:
                printf("enter the data part of the node that you want to delete : ");
                scanf("%d",&temp);
                start=Delete(start,&last,temp);
                break;
            case 7:
                if(last==NULL)
                {
                    printf("the list is empty...you can't delete any node...");
                    break;
                }
                start=deleteLast(start,&last);
                break;
            case 8:
                start=reverseList(start,&last);
                break;
            case 9:
                start=sort(start,&last);
                break;
            case 10:
                start=sort2(start,&last);
                break;
            case 11:
                exit(1);
            default:
                printf("you have entered a wrong choice...enter a valid choice");
        }
    }
}

Node* createNode(int data)
{
    Node*newNode;
    newNode=(Node*)malloc(sizeof(Node));
    newNode->data=data;
    newNode->next=NULL;
    return newNode;
}

Node*insertLast(Node*start,Node**p2last,Node*newNode)
{
    if(*p2last==NULL)
    {
        *p2last=newNode;
        return newNode;
    }
    (*p2last)->next=newNode;
    *p2last=newNode;
    return start;
}

void printList(Node*start)
{
    printf("your list is as follows : \n");
    while(start)
    {
        printf("%d\t",start->data);
        start=start->next;
    }
}

int search(Node*start,int data)
{
    while(start)
    {
        if(start->data==data)
            return 1;
        start=start->next;
    }
    return 0;
}

void insertAfter(Node*start,Node**p2last,int data,int num)
{
    Node*newNode,*tmp;
    newNode=createNode(num);
    if(*p2last==NULL)
        printf("the list is empty...");
    tmp=start;
    while(tmp)
    {
        if(tmp->data==data)
            break;
        tmp=tmp->next;
    }
    if(!tmp)
        printf("the number you enter was not in the list\n");
    else
    {
        newNode->next=tmp->next;
        tmp->next=newNode;
        if(tmp==*p2last)
            *p2last=newNode;
    }
}

Node*insertBefore(Node*start,int data,int num)
{
    Node *newNode,*prev,*tmp;
    prev=NULL;
    newNode=createNode(num);
    if(start==NULL)
    {
        printf("the list is empty...");
        return start;
    }
    tmp=start;
    while(tmp)
    {
        if(tmp->data==data)
            break;
        prev=tmp;
        tmp=tmp->next;
    }
    if(!tmp)
        printf("the number you enter was not in the list\n");
    else if(prev==NULL)
    {
        newNode->next=start;
        start=newNode;
    }
    else
    {
        newNode->next=prev->next;
        prev->next=newNode;
    }
    return start;
}

Node*Delete(Node*start,Node**p2last,int data)
{
    Node*prev,*tmp;
    tmp=start;
    prev=NULL;
    while(tmp)
    {
        if(tmp->data==data)
            break;
        prev=tmp;
        tmp=tmp->next;
    }

    if(!tmp)
    {
        printf("the item you entered was not in the list...\n");
        return start;
    }
    if(tmp==start)
    {
        if((*p2last)==start)
            *p2last=NULL;
        return NULL;
    }
    prev->next=tmp->next;
    if(tmp==(*p2last))
        *p2last=prev;
    free(tmp);

    return start;
}

Node*deleteLast(Node*start,Node**p2last)
{
    return Delete(start,p2last,(*p2last)->data);
}

Node*reverseList(Node*start,Node**p2last)
{
    Node*ptr,*tmp,*prev;
    (*p2last)=start;
    prev=NULL;
    for(ptr=start;ptr;)
    {
        tmp=ptr->next;
        ptr->next=prev;
        prev=ptr;
        ptr=tmp;
    }
    return prev;
}

Node*sort(Node*start,Node**p2last)
{
    Node*ptr,*newNode,*tmp,*start1,*last1;
    start1=last1=NULL;
    while(start!=NULL)
    {
        tmp=ptr=start;
        while(ptr)
        {
            if(tmp->data > ptr->data)
                tmp=ptr;
            ptr=ptr->next;
        }
        newNode=createNode(tmp->data);
        start1=insertLast(start1,&last1,newNode);
        start=Delete(start,p2last,tmp->data);
    }
    *p2last=last1;
    return start1;
}

Node*sort2(Node*start,Node**p2last)
{
    int *arr,count=0,i,tmp,j;
    Node*ptr,*start1,*last1,*newNode;
    ptr=start;
    start1=last1=NULL;
    while(ptr)
    {
        count++;
        ptr=ptr->next;
    }

    arr=(int*)malloc(sizeof(int)*count);
   
    ptr=start;
    for(i=0;i<count;i++)
    {
        arr[i]=ptr->data;   
        ptr=ptr->next;
    }
   
    /* sorting the array bubble */
    for(i=1;i<count;i++)
        for(j=0;j<count-i;j++)
            if(arr[j]>arr[j+1])
            {
                tmp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=tmp;
            }
   
    for(i=0;i<count;i++)
        start1=insertLast(start1,&last1,createNode(arr[i]));
    *p2last=last1;
    return start1;
}
/*************************************************************************/

PROJECT EULER SOLUTION # 89

Solution to problem number 89 of Project Euler.

Question # 89

 

The rules for writing Roman numerals allow for many ways of writing each number (see About Roman Numerals...). However, there is always a "best" way of writing a particular number.
For example, the following represent all of the legitimate ways of writing the number sixteen:

IIIIIIIIIIIIIIII
VIIIIIIIIIII
VVIIIIII
XIIIIII
VVVI
XVI

The last example being considered the most efficient, as it uses the least number of numerals.
The 11K text file, roman.txt (right click and 'Save Link/Target As...'), contains one thousand numbers written in valid, but not necessarily minimal, Roman numerals; that is, they are arranged in descending units and obey the subtractive pair rule (see About Roman Numerals... for the definitive rules for this problem).
Find the number of characters saved by writing each of these in their minimal form.

Note: You can assume that all the Roman numerals in the file contain no more than four consecutive identical units.

About Roman Numerals:-

Traditional Roman numerals are made up of the following denominations:

I = 1
V = 5
X = 10
L = 50
C = 100
D = 500
M = 1000

You will read about many different rules concerning Roman numerals, but the truth is that the Romans only had one simple rule:

Numerals must be arranged in descending order of size.

For example, three ways that sixteen could be written are XVI, XIIIIII, VVVI; the first being the preferred form as it uses the least number of numerals.
The "descending size" rule was introduced to allow the use of subtractive combinations. For example, four can be written IV because it is one before five. As the rule requires that the numerals be arranged in order of size it should be clear to a reader that the presence of a smaller numeral out of place, so to speak, was unambiguously to be subtracted from the following numeral. For example, nineteen could be written XIX = X + IX (9). Note also how the rule requires X (ten) be placed before IX (nine), and IXX would not be an acceptable configuration.
Generally the Romans tried to use as few numerals as possible when displaying numbers. For this reason, XIX would be the preferred form of nineteen over other valid combinations, like XVIIII or XVIV. However, this was NOT a rule and there still remain in Rome many examples where economy of numerals has not been employed. For example, in the famous Colesseum the the numerals above the forty-ninth entrance is written XXXXVIIII and not IL nor XLIX (see rules below).
Despite this, over time we have continued to introduce new restrictive rules. By mediaeval times it had become standard practice to avoid more than three consecutive identical numerals. That is, IV would be written instead of IIII, IX would be used instead of VIIII, and so on. In addition, the subtractive combinations had the following rules superimposed:

1. Only I, X, and C can be used as the leading numeral in part of a subtractive pair.
2. I can only be placed before V and X.
3. X can only be placed before L and C.
4. C can only be placed before D and M.

These last four rules are considered to be law, and generally it is preferred, but not necessary, to display numbers using the minimum number of numerals. Which means that IL is considered an invalid way of writing forty-nine, and whereas XXXXVIIII, XXXXIX, XLVIIII, and XLIX are all quite legitimate, the latter is the preferred (minimal) form.
It is also expected that higher denominations should be used whenever possible; for example, L should be used in place of XXXXX, or C should be used in place of LL. However, even this "rule" has been flaunted: in the church of Sant'Agnese fuori le Mura (St Agnes' outside the walls), found in Rome, the date, MCCCCCCVI (1606), is written on the gilded and coffered wooden ceiling; I am sure that many would argue that it should have been written MDCVI.
However, if we believe the adage, "when in Rome do as the Romans do," and we see how the Romans write numerals, then it clearly gives us much more freedom than many would care to admit.

Solution:-

/*************************************************************************/

/*
    solution to project euler 89
*/
#include<string.h>
#include<stdio.h>

int findNumber(char*);
int findRoman(int);

int main()
{
    FILE *fp;
    char str[100];
    int n,i,counter,sum;
    if(fp=fopen("a.txt","r"))
    {
        while(!feof(fp))
        {
            //counter=0;
            i=0;
            fscanf(fp,"%s",str);
            counter=strlen(str);
            str[counter]='\0';
            //printf("%s\n",str);
            sum+=counter-findRoman(findNumber(str));
            str[0]='\0';
        }
        printf("answer = %d\n",sum);
    }
    else
        printf("there was an error in opening the file...aborting...");

    return 0;
}


int findRoman(int n)
{
    int counter=0;
    //printf("%d => ",n);
    while(n>=1000)
    {
        counter++;
        //printf("M");
        n-=1000;
    }
    if(n>=900)
    {
        counter+=2;
        //printf("CM");
        n-=900;
    }
    if(n>=500)
    {
        counter++;
        //printf("D");
        n-=500;
    }
    if(n>=400)
    {
        counter+=2;
        //printf("CD");
        n-=400;
    }
    if(n<400)
        while(n>=100)
        {
            counter++;
            //printf("C");
            n-=100;
        }
    if(n>=90)
    {
        counter+=2;
        //printf("XC");
        n-=90;
    }
    if(n>=50)
    {
        counter++;
        //printf("L");
        n-=50;
    }
    if(n>=40)
    {
        counter+=2;
        //printf("XL");
        n-=40;
    }
    if(n<40)
        while(n>=10)
        {
            counter++;
            //printf("X");
            n-=10;
        }
    if(n==9)
    {
        counter+=2;
        //printf("IX");
        n-=9;
    }
    if(n>=5)
    {
        counter++;
        //printf("V");
        n-=5;
        //printf("%d",n);
    }
    if(n==4)
    {
        counter+=2;
        //printf("IV");
        n-=4;
    }
    while(n!=0)
    {
        counter++;
        //printf("I");
        n--;
        //printf("%d\n",n);
    }
    //printf("\n");
    return counter;
}



int findNumber(char *str)
{
    int i=0,n=0,x;
    for(x=0;x<2;x++)
    {
        if(str[i] && str[i+1] && str[i]=='C' && str[i+1]=='M')
        {
            i+=2;
            n+=900;
        }

        while(str[i] && str[i]=='M')
        {
            n+=1000;
            i++;
        }
    }

    for(x=0;x<2;x++)
    {
        if(str[i] && str[i+1] && str[i]=='C' && str[i+1]=='D')
        {
                i+=2;
                n+=400;
        }

        while(str[i] && str[i]=='D')
        {
                n+=500;
                i++;
        }
    }

    for(x=0;x<2;x++)
    {
        if(str[i] && str[i+1] && str[i]=='X' && str[i+1]=='C')
        {
                i+=2;
                n+=90;
        }

        while(str[i] && str[i]=='C')
        {
                n+=100;
                i++;
        }
    }

    for(x=0;x<2;x++)
    {
        if(str[i] && str[i+1] && str[i]=='X' && str[i+1]=='L')
        {
                i+=2;
                n+=40;
        }

        while(str[i] && str[i]=='L')
        {
                n+=50;
                i++;
        }
    }

    for(x=0;x<2;x++)
    {
        if(str[i] && str[i+1] && str[i]=='I' && str[i+1]=='X')
        {
                i+=2;
                n+=9;
        }

        while(str[i] && str[i]=='X')
        {
                n+=10;
                i++;
        }
    }

    for(x=0;x<2;x++)
    {
        if(str[i] && str[i+1] && str[i]=='I' && str[i+1]=='V')
        {
                i+=2;
                n+=4;
        }

        while(str[i] && str[i]=='V')
        {
                n+=5;
                i++;
        }
    }

    while(str[i] && str[i]=='I')
    {
        n++;
        i++;
    }

    return n;
}

/*************************************************************************/

 

PROJECT EULER SOLUTION # 65

Solution to problem number 65 of Project Euler
Question # 65

The square root of 2 can be written as an infinite continued fraction.

2 = 1 +	1
	2 +	1
		2 +	1
			2 +	1
				2 + ...

The infinite continued fraction can be written, 2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, 23 = [4;(1,3,1,8)].
It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for 2.

1 +	1	= 3/2
	2

1 +	1		= 7/5
	2 +	1
		2

1 +	1			= 17/12
	2 +	1
		2 +	1
			2

1 +	1				= 41/29
	2 +	1
		2 +	1
			2 +	1
				2

Hence the sequence of the first ten convergents for 2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, ...

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...].
The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, ...

The sum of digits in the numerator of the 10^th convergent is 1+4+5+7=17.
Find the sum of digits in the numerator of the 100^th convergent of the continued fraction for e.

Solution:-

/****************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#define max 100
int n[max]={0},pn[max]={0};
void fun(int);
void print(int*);
void assignArray(int*,int*);
void add(int*,int*);

int main()
{
    int i,sum=0;
    for(i=1;i<=100;i++)
    {
        fun(i);
        /*
        printf("i=%d=>",i);
        print(n);
        */
    }
    for(i=0;i<max;i++)
        sum+=n[i];
    printf("answer = %d\n",sum);
    return 0;
}

void print(int *arr)
{
    int flag=0,i;
    for(i=0;i<max;i++)
    {
        if(arr[i] || flag)
        {
            flag=1;
            printf("%d",arr[i]);
        }
    }
    printf("\n");
}

void add(int*a,int*b)
{
    int i;
    for(i=max-1;i>0;i--)
    {
        a[i]+=b[i];
        if(a[i]>9)
        {
            a[i]%=10;
            a[i-1]+=1;
        }
    }
}

void assignArray(int*a,int*b)
{
    int i;
    for(i=0;i<max;i++)
        a[i]=b[i];
}

void fun(int x)
{
    long long int flag;
    int i,tmpn[max]={0},tmpArr[max]={0};
    if(x==1)
    {
        n[max-1]=2;
        return;
    }
    if(x==2)
    {
        pn[max-1]=2;
        n[max-1]=3;
        return;
    }

    if(x%3==0)
    {
        assignArray(tmpn,n);
        flag=(x/3)*2;
   
        for(i=0;i<flag;i++)
            add(tmpArr,n);

        add(tmpArr,pn);
        assignArray(n,tmpArr);

        assignArray(pn,tmpn);
        return;
    }

    assignArray(tmpn,n);
    add(n,pn);
    assignArray(pn,tmpn);
}
/****************************************************************************/

PROJECT EULER SOLUTION # 29

Solution to problem number 29 of Project Euler
Question # 29
Consider all integer combinations of a^b for 2 a 5 and 2 b 5:

2²=4, 2³=8, 2⁴=16, 2⁵=32
3²=9, 3³=27, 3⁴=81, 3⁵=243
4²=16, 4³=64, 4⁴=256, 4⁵=1024
5²=25, 5³=125, 5⁴=625, 5⁵=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by a^b for 2 a 100 and 2 b 100?

Solution # 29

/****************************************************************/

#include<stdio.h>

#include<math.h>

int a,b;

struct pair

{

      int x,y;

};

struct pair p[9801];

int isEqual(int,int);

void setToBasic(int);

int main()

{

      int i,j,counter=0,answer;

      for(i=2;i<=100;i++)

            for(j=2;j<=100;j++)

            {

                  p[counter].x=i;

                  p[counter].y=j;

                  counter++;

            }

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

            setToBasic(i);

      answer=9801;

      for(i=9800;i>=0;i--)

            for(j=i-1;j>=0;j--)

                  if(p[i].x && p[i].y && isEqual(i,j))

                        answer--;

      printf("answer = %d\n",answer);

      return 0;

}

int isEqual(int i,int j)

{

      if(p[i].x==p[j].x && p[i].y==p[j].y)

      {

            p[j].x=p[j].y=0;

            return 1;

      }

      return 0;

}

void setToBasic(int counter)

{

      int i,j;

      for(i=2;i<p[counter].x;i++)

            for(j=2;pow(i,j)<=p[counter].x;j++)

                  if(pow(i,j)==p[counter].x)

                  {

                        p[counter].x=i;

                        p[counter].y*=j;

                  }

}

/****************************************************************/

Maxim and Dividers - Solution

Problem Statement

Maxim likes dividers of the numbers. Also Maxim is fond of lucky numbers of small elephant from Lviv city.

If you remember, lucky numbers are positive integers whose decimal representation contains only the lucky digits 4 and 7. For example, numbers 47, 744, 4 are lucky, 5, 17, 467 — aren't.

Now Maxim is interested in the next information: what is the number of the integer positive dividers of number n, which are overlucky.

We call number overlucky if it is possible to remove some, but not all, digits and during bonding the remaining digits we will receive a lucky number. For example, number 72344 — overlucky, because it is possible to remove digits 2 and 3, and get number 744, which is lucky. Number 223 isn't overlucky.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. Single line of each test case contains an integer n.

Output

For each test case on different lines print the answer to the problem.

Constraints

• 1 ≤ T ≤ 10
• 1 ≤ n ≤ 10^9

Example

Input:

10

1

2

3

4

5

6

7

8

9

10

Output:

0

0

0

1

0

0

1

1

0

0

Solution:

#include<stdio.h>

int isOverLucky(int);

int fun(int);

int main()

{

        int i,t,num,j;

        scanf("%d",&t);

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

        {

               scanf("%d",&num);

               printf("%d\n",fun(num));

        }

        return 0;

}

int isOverLucky(int n)

{

        while(n)

        {

               if(n%10==4 || n%10==7)

                       return 1;

               n/=10;

        }

        return 0;

}

int fun(int n)

{

        int i,counter=0;

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

               if(n%i==0)

                       counter+=isOverLucky(i)+isOverLucky(n/i);

        if(n%i==0)

               counter+=isOverLucky(i);

        return counter;

}