You are not logged in. Please login at www.codechef.com to post your questions!

×

FEST03 - Editorial

Problem Link: CONTEST PRACTICE

Author- Sameer Taneja
Tester- Vipin Khushu
Editorialist- Kushank Arora

Difficulty:
Simple

Prerequisites:
Hashing

Problem:
The aim is to find 3 characters which has the maximum frequency and their corresponding frequencies.

Explanation:
The problem is to find 3 characters which has the maximum frequency. For this purpose, we need to have the frequency of all the characters. Before finding the frequency of every character, let us take an example to understand how frequency for each character is calculated? This is done using Hashing.
For an example, if there is a row in which 1000 people are standing each holding a card which is either red, green, blue or black. And the person has to note the number of people having the red card or green card or blue card or black card, the person makes 4 trays and ask each person to place their card in corresponding plates. Then he can easily find the number of cards for each color.
Similarly in our case, we will make 26 trays and each character in the string which deposit their identity in corresponding trays. This is done in this way:
tray[26] = 0 //Each element in the array is assigned zero
for i in len(str):
    if(str[i] = ’a’ or str[i] = ’A’):
        tray[0] = tray[0] + 1
    else if(str[i] = ’b’ or str[i] = ’B’):
        tray1 = tray1 + 1
so on c,d,e....y
    else if(str[i] = ’z’ or str[i] = ’Z’):
        tray[25] = tray[25] + 1

The above code is not the efficient code as it requires so many ifs and elses. Thus to make it efficient, we first convert the character to upper case(or lower case) and then decrement its ASSCII value by the ASCII value of ‘A’ (as the letters are consecutive in ASSCII). This gives us a number ranging from 0 to 25 where 0 is for A and 25 for Z. Thus or code becomes:
tray[26] = 0 //Each element in the array is assigned zero
for i in len(str):
    if UPPER(str)>=’A’ and UPPER(str)<=’Z’ :
        tray[UPPER(str[i]) – ‘A’] = tray[UPPER(str[i]) – ‘A’] + 1

Next step is to, find the maximum 3 of the array. For this firstly the maximum from the array is found and it is removed from the array. Then again the new maximum is found, and so on, till we have 3 maxima.

i = 0
while i < 3 :
    j=0     max=0
    while j < 26:
        if(tray[j]>tray[max]):
            max = j
            j = j + 1
//max has the index of the character with maximum frequency, Use it here.
    tray[max] = -1
    i = i +1

Solution
http://ideone.com/wjwZem

asked 29 Mar '16, 11:39

vipinkhushu's gravatar image

3★vipinkhushu
51
accept rate: 0%

edited 04 Apr '16, 15:42

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×1,191
×344
×10
×1

question asked: 29 Mar '16, 11:39

question was seen: 867 times

last updated: 04 Apr '16, 15:42