# UVA Problem 10008 – What’s Cryptanalysis? Solution

UVA Problem 10008 – What’s Cryptanalysis? Solution:

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;

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;
}
```