UVA Problem 10008 – What’s Cryptanalysis? Solution

Posted on by quickgrid
See More

UVA Problem 10008 – What’s Cryptanalysis? Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

Task for this problem is to find occurrence of each alphabetical character. Uppercase and lowercase are treated as same characters. No other characters except for upper and lower case characters must be counted.

After counting their occurrence print them in most to least order. If multiple characters have same character count then print the characters alphabetically. Ex: If E occurred 2 times, A occurred 2 times then, print A first then E.
 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

3
This is a test.
Count me 1 2 3 4 5.
Wow!!!! Is this question easy?

 

Output:

S 7
T 6
I 5
E 4
O 3
A 2
H 2
N 2
U 2
W 2
C 1
M 1
Q 1
Y 1

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 10008 - What's Cryptanalysis
 * Technique: Counting character occurrence in string,
 *            Lexicographical / alphabetically sort characters,
 */


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


#define N 256


// Holds each character and its occurrence in string.
struct collection{
    char character;
    int occurence;
} node[26];


static char s[N];


// Sorts based on occurrence, if occurrence count is same
// then sort using lexicographical / alphabetically first character.
int cmp(collection a, collection b){

    if(a.occurence < b.occurence)
        return 0;
    else if(a.occurence > b.occurence)
        return 1;
    else
        return (a.character <= b.character) ? 1 : 0;

}



int main(){

    // O(1)
    // Represent character by its ASCII value index.
    for(int i = 'A'; i <= 'Z'; ++i)
        node[i].character = i;

    int n;

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

    while( n-- ){

        gets( s );

        // Convert string to uppercase O(n)
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'a' && s[i] <= 'z')
                s[i] = s[i] - 32;
        }


        // O(n)
        // Counting using character index
        for(int i = 0; s[i]; ++i){
            if( s[i] >= 'A' && s[i] <= 'Z' )
                ++node[ s[i] ].occurence;
        }

    }


    // Sorts occurrence most to least and in lexicographic order.
    std::sort(node + 'A', node + 'Z', cmp);


    // O(1)
    // Prints sorted occurrence most to least.
    // Also prints characters in lexicographic
    // order if two occurrence are same.
    for(int i = 'A'; i <= 'Z'; ++i){
        if(node[i].occurence)
            printf("%c %d\n", node[i].character, node[i].occurence);
    }



    return 0;
}

UVA Problem 424 – Integer Inquiry Solution

Posted on by quickgrid

UVA Problem 424 – Integer Inquiry Solution:

Click here to go to this problem in uva Online Judge.

Solving Technique:

This problem requires adding integers. The integers are very long, meaning they won’t fit even in long long. So the addition needs to be done using arrays.

It can be solved using integers arrays but my solution uses character array. Code is explained in the comments.

Similar to this problem UVA 10035 Primary Arithmetic and UVA 713 – Adding Reversed Numbers.

 

Important:  Be sure to add or print a new line after each output unless otherwise specified. The outputs should match exactly because sometimes even a space character causes the answer to be marked as wrong answer. Please compile with c++ compiler as some of my codes are in c and some in c++.

More Inputs of This Problem on uDebug.

Input:

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0

 

Output:

370370367037037036703703703670

Code:

/**
 * Author:    Asif Ahmed
 * Site:      https://quickgrid.wordpress.com
 * Problem:   UVA 424 - Integer Inquiry
 * Technique: Adding Multi String Integer characters column wise
 */


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

#define N 160


static char s[N][N];
static char output[N];



int main(){

    int i = 0;

    int maxlen = 0;


    // Finish taking all the inputs.
    while( gets(s[i]) ){

        // Exit for input of 0.
        if( s[i][0] == '0' && ! s[i][1] )
            break;

        int len = strlen( s[i] );

        // Get the max length to create padding.
        if( len > maxlen )
            maxlen = len;

        ++i;
    }

    // Save rows
    int rows = i;


    // Create padding for each of the strings.
    for(int j = 0; j < i; ++j){

        int temp = strlen( s[j] );

        if( temp != maxlen ){

            // Shift by this many spaces to create 0's in front.
            int padding = maxlen - temp;

            // shift by padding columns.
            for(int k = temp - 1; k >= 0; --k)
                s[j][k + padding] = s[j][k];

            // Add 0's as paddings.
            for(int k = 0; k < padding; ++k)
                s[j][k] = '0';
        }
    }


    int carry = 0, z = 0;

    for(int j = maxlen - 1; j >= 0; --j){

        int sum = 0;

        // Add values column wise.
        for(int i = 0; i < rows; ++i)
            sum += s[i][j] - '0';

        // Add if any previous  carry
        sum = sum + carry;

        // Add value to output
        output[z++] = sum % 10 + '0';

        // get the carry for adding to next column
        carry = sum / 10;

    }

    // Print if any carry first
    if(carry)
        printf("%d", carry);


    // Then print what ever character is left
    for(int i = z - 1; i >= 0; --i){
        if(output[i] >= '0' && output[i] <= '9')
            printf("%c", output[i]);
    }
    printf("\n");

    return 0;
}