English word, Kate has downloaded a translation software. It works in a simple principle.

QUESTION

Kate has downloaded a translation software. It works in a simple principle, it is used to translate an English word by simply replacing it by its corresponding Japanese word. (assume there’s only one corresponding Japanese word for one English word)

More specifically, the software will look into its internal memory first to see if there already has been its translated word stored. If so, the software will directly use it. Otherwise, the software will search the English word in an external dictionary, use the search result (assume that the dictionary contains everything), as well as store the translated word into internal memory for preparation of translating another same English word.

Suppose that there are ‘m’ storage units in the internal memory and each of them can store a word and its corresponding Japanese word. For each new translated word to be stored if there is any empty units, the software will allocate one for this word.  Otherwise, the software will remove the word stored earliest and use the unit freed to store the new word.  

Kate has used this software to translate an essay of ‘n’ words and she would like to know how many times the translation software would turn to the external dictionary during its translation of the whole essay. Assume that there is no translated word stored in the internal memory at the beginning.

 Input:

The input data contains two lines, the first line contains 2 integers separated by a space denoting ‘m’, ‘n’.  The second line contains n non-negative integers not exceeding 1000 separated by spaces. Each integer represents a word in the paper.  Two words are considered the same if and only if the corresponding integers are equal.  

Output:

One integer in a line denoting the times that the software would turn to the external dictionary.  

Sample Input:

3    7

1    2    1    5    4    4    1

Sample Output:

5

Constraint

1<=m<=100 , 1<=n <=1000

 

 

SUMMARY

Internal storage having ‘m’ fields and a sentence containing ‘n’ words is taken as input to this program. While we translate each word from English to Japanese, if the word translation is found in this internal storage it is used directly and if not, its translation is found in an external dictionary and is loaded into the internal storage. The number of times the external dictionary is referred to is counted and printed as the output.

 

 

EXPLANATION

The variables m and n are taken as input from the user. An array ‘a’ is declared and will contain the input of integers indicating the ‘n’ words of the input sentence. Another array ‘b’ is declared to have the internal storage integers. If array ‘b’ is overloaded, the number initially stored will be removed and the place will be occupied by a new one.

Every word in input is checked if it is already present in ‘b’. If it is, then it’s ignored, or else the integer will be added to it and the count will be incremented. Count indicates the number of external checks for translation(number of times the external dictionary is referred to, to translate). The count is then printed as the output.

 

 

CODE

#include <iostream>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    int a[n];
    for(int j=0;j<n;j++)
    cin>>a[j];
    int b[1000];
    for(int j=0;j<m;j++)
    b[j]=-1;
    b[0]=a[0];
    int c=1;
    int count=1;
    for(int i=1;i<n;i++)
    {
        bool bo=false;
        for(int j=0;j<m;j++){
            if(b[j]==a[i]){
                bo=true;
                break;
            }
        }
        if(bo==false){
            if(c==m){
                c=0;
            }
            b[c]=a[i];
            c++;
            count++;
        }
    }
    /* printing the output */
    cout<<count<<endl;
}
 

 

OUTPUT

 

Also Read: Implement a bag class using a linked list