Integer In Words Conversion

The problem is given a number (upto a certain range) we need to convert the number in words.

Example:

1. 999 -> Nine Hundred Ninety-Nine
2. 4 -> Four
3. 0 -> Zero
4. -230 -> Minus Two Hundred Thirty.
5. 40 -> Forty

C Implementation

#include <stdio.h>

void print(int arr[], int n)
{
    int m, i;
    char *unit[] = {"","One","Two","Three","Four","Five","Six",
                    "Seven","Eight","Nine"};
    char *ten[] = {"","Ten","Twenty","Thirty","Forty",
                    "Fifty","Sixty","Seventy","Eighty","Ninety"};
    char *hundred[] = {"Ten","Eleven","Twelve","Thirteen","Fourteen",
                    "Fifteen","Sixteen","Seventeen","Eighteen","Nineteen"};
    
    for(i = 0; i < 5; i++) {
        if(i != 3) {
            if(arr[i]) {
                if((arr[i]%10) != 0) {
                    if(arr[i] < 10)
                        printf("%s ",unit[arr[i]]);
                    else if(arr[i] <= 19)
                        printf("%s ",hundred[arr[i]%10]);
                    else
                        printf("%s-%s ",ten[arr[i]/10],unit[arr[i]%10]);
                }
                else
                    printf("%s ",ten[arr[i]/10]);
                switch(i) {
                case 0: printf("Coror ");break;
                case 1: printf("Lakh ");break;
                case 2: printf("Thousand ");
                }
            }
        }
        else if(arr[3]) {
            printf("%s ",unit[(arr[i])]);
            printf("Hundred ");
        }
    }
    printf("\b.");
}

void divide(long int temp)
{
    int arr[10], i;
    long int div = 10000000;
    for(i = 0; i < 5; i++) {
        arr[i] = temp/div;
        temp = temp%div;
        if(i == 2) div /= 10;
        else div /= 100;
    }
    print(arr, 10);
}

int main(void)
{
    int i,j;
    long int num,temp;

    printf("Enter A Number(9-dig): ");
    scanf("%lld",&num);
    
    temp = (num < 0)? (-1 * num) : num;

    printf("In Words: ");
    if(num < 0) {
        printf("Minus ");
        divide(temp);
    }
    else if(num == 0) {
        printf("Zero.");
    }
    else {
        divide(temp);
    }
    return 0;
}

Enter A Number(9-dig): 3
In Words: Three.

Enter A Number(9-dig): 120
In Words: One Hundred Twenty.

Enter A Number(9-dig): 0
In Words: Zero.

Enter A Number(9-dig): -120
In Words: Minus One Hundred Twenty.

Enter A Number(9-dig): 99999
In Words: Ninety-Nine Thousand Nine Hundred Ninety-Nine.

Enter A Number(9-dig): 999999
In Words: Nine Lakh Ninety-Nine Thousand Nine Hundred Ninety-Nine.

Enter A Number(9-dig): 9999999
In Words: Ninety-Nine Lakh Ninety-Nine Thousand Nine Hundred Ninety-Nine.

Enter A Number(9-dig): 002
In Words: Two.

Program To Check Whether A Graph (Undirected) Is Connected Or Not

---

Connected Component

---

For a undirected graph it is easy to check that if the graph is connected or not. To check that a graph is connected or not. We can simply do a depth-first traversal or a breadth first-first traversal on the graph and if the traversal successfully traversal all the nodes in the graph then we can conclude that the graph is connected else the graph has components. This way we can also count the number of components.

For Example:

G	G'

Here G is connected and has one component. But G' is not connected and has two component. 

---

C Implementation

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

#include <stdio.h> #include <stdlib.h> #define TRUE 1 #define FALSE 0 //Function to create a graph... void createGraph(int G[][50], int v) { int i, j; printf("\nEnter The Adjacency Matrix: \n"); for(i = 0; i < v; i++) { for(j = 0; j < v; j++) { scanf("%d",&G[i][j]); } } } //Function to print the graph... void printGraph(int G[][50], int v) { int i, j; for(i = 0; i < v; i++) { putchar('['); for (j = 0; j < v; j++) printf("%3d ",G[i][j]); putchar(']'); putchar('\n'); } } //Function for Depth first search... void DFS(int G[][50], int i, int visited[], int v) { int u; visited[i] = TRUE; for(u = 0; u < v; u++) if(G[i][u] == TRUE && visited[u] != TRUE) DFS(G, u, visited, v); } //Call DFS on each single vertex and count the " #(calls) = #(components) "... int visitAll(int G[][50], int v) { int i, visited[50], count = 0; for(i = 0; i < v; i++) visited[i] = FALSE; for(i = 0; i < v; i++) { if(visited[i] != TRUE) { ++count; DFS(G, i, visited, v); } } return count; } //Checks if the graph is connected or not... int isConnected(int G[][50], int v) { return ((visitAll(G, v) > 1)? FALSE : TRUE); } int main() { int G[50][50], v, e; printf("Enter The Number Of Vertices: "); scanf("%d",&v); createGraph(G, v); printf("\nThe Adjacency Matrix:\n\n"); printGraph(G, v); printf("\n\nThe Given Graph Is%sConnected.",isConnected(G, v)?" ":" Not "); printf("\n\nThere Are %d Components.",visitAll(G, v)); return 0; }

---

Output

---

First Run(G):

Enter The Number Of Vertices: 4

Enter The Adjacency Matrix:

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

The Adjacency Matrix:

[  0   1   1   1 ]

[  1   0   1   1 ]

[  1   1   0   1 ]

[  1   1   1   0 ]

The Given Graph Is Connected.

There Are 1 Components.

Second Run(G'):

Enter The Number Of Vertices: 4

Enter The Adjacency Matrix:
0 0 0 0
0 0 0 1
0 0 0 1
0 1 1 0

The Adjacency Matrix:

[  0   0   0   0 ]
[  0   0   0   1 ]
[  0   0   0   1 ]
[  0   1   1   0 ]


The Given Graph Is Not Connected.

There Are 2 Components.

Fully Parenthesized Infix Expression From Postfix Expression

The problem is that you are given a post fix expression and you need to convert it to a fully parenthesize infix expression.

Exmple:

• Input: ab+
• Output: (a+b)

The approach used in this program is to print the parenthesis durin infix traversal of the expression tree built from the postfix expression.

#include <iostream>
#include <stack>

using namespace std;

typedef struct Node
{
    char data;
    Node *lChild, *rChild;
}Node;

class ExpressionTree
{
    private:
        Node *root;
    public:
        ExpressionTree() { root = NULL; }
        ExpressionTree(char[]);
        Node* getRoot() { return root; }
        Node* createNode(char , Node*, Node*);
        friend bool isOperator(char);
        friend void inOrder();
};

bool isOperator(char opp)
{
    switch(opp)
    {
        case '+':
        case '*':
        case '/':
        case '^':
        case '-':
            return true;
        default:
            return false;
    }
}

Node* ExpressionTree::createNode(char ch, Node *l, Node *r)
{
    Node *tmp = new Node();
    tmp->data = ch;
    tmp->lChild = l;
    tmp->rChild = r;
    return tmp;
}

ExpressionTree::ExpressionTree(char arr[])
{
    stack<Node*> s;
    Node *ptr, *l, *r;
    int i = 0;
    while(arr[i])
    {
        if(isOperator(arr[i]))
        {
            l = s.top();
            s.pop();
            r = s.top();
            s.pop();
            ptr = createNode(arr[i], r , l);
        }
        else
        {
            ptr = createNode(arr[i], NULL, NULL);
        }
        s.push(ptr);
        i++;
    }
    root = s.top();
}


void inOrder(Node* T)
{
    if(T != NULL)
    {
        if(isOperator(T->data)) cout << "(";

        inOrder(T->lChild);
        cout << T->data;
        inOrder(T->rChild);

        if(isOperator(T->data)) cout << ")";
    }
}

int main()
{
    char exp[50];
    
    cout << "Enter A Postfix Expression:" << ends;
    cin >> exp;
    
    ExpressionTree t(exp);
    
    cout << "Given Postfix Expression:" << ends;
    cout << exp << endl;
    
    cout << "In-order Form: " << ends;
    inOrder(t.getRoot());
    
    return 0;
}

Enter A Postfix Expression: ab+c*
Given Postfix Expression: ab+c*
In-order Form:  ((a+b)*c)
--------------------------------
Process exited after 6.555 seconds with return value 0
Press any key to continue . . .

Programming Problem Two

Problem Statement:   Shashank likes strings in which consecutive characters are different. For example, he likes ABABA, while he dosen't like ABAA. Given a string congaing characters A and B only, he wants to change it to a string he likes. To do so he is allowed to delete the characters in the string. The problem is to fin d the minimum number of deletion required.

For example:

ABBAB -> ABAB (Requires 1 deletion)
AAAAAA -> NULL (Requires 6 deletion)
ABABA -> ABABA (Requires 0 deletion)

C++ Code:

1. #include <iostream>
2. #include <string>
3. #include <cstring>
4. using namespace std;
5. 
   
6. int delRequired(string testString)
7. {
8. size_t size = testString.length();
9. char arr[size+1];
10. strcpy(arr,testString.c_str());
11. int i, noOfDel = 0;
12. for(i = 0; i < size; ++i) {
13. if(arr[i] == arr[i+1]) {
14. noOfDel += 1;
15. }
16. }
17. return noOfDel;
18. }
19. 
    
20. int main()
21. {
22. int testCase, i = 0;
23. cin >> testCase;
24. int delArr[testCase];
25.  
26. while(testCase--) {
27. string testString;
28. cin >> testString;
29. delArr[i++] = delRequired(testString);
30. }
31. delArr[i] = -1;
32. i = 0;
33. while(delArr[i] != -1) {
34. cout << delArr[i] << endl;
35. i += 1;
36. }
37. return 0;
38. }

Programming Problem One

Problem Statement:   Given two numbers (int) L (low) and H (high) , The problem is to find the maximum value of A xor B such that  L ≤ A ≤ B ≤ U.

C++ Code:

1. #include <iostream>
2. using namespace std;
3. 
   
4. int maxXor(int l, int r) 
5. {
6. int max = 0;
7. for (int i = l; i <= r; ++i) {
8. for (int j = l; j <= r; ++j) {
9. if((i ^ j) >= max) {
10. max = i ^ j;
11. }
12. }
13. }
14. return max;
15. }
16.  
17. int main() 
18. {
19. int res, l, r;
20.  
21. cin >> l;
22. cin >> r;
23.  
24. res = maxXor(l, r);
25. cout << res;
26.   return 0;
27. }