Mike_And_HashTrick

#1


sir why my code is giving wrong anwers.

#2

Hello @rajukumarbhui

THE PROBLEM
The Hash function given on the coding Blocks website is wrong.
First the array “hash” should be of size MAX + 1 because we are accessing the index MAX also.

Your code is correct according to the question.
If you print the hashes of all the distinct integers in the array, for the testcase
6
1 2 3 1 2 3
// You can use https://ide.codingblocks.com/s/160567 to run the test case. I have added the code to print the hash values.

You would see that hash for
1 is zero
2 is zero
3 is two

Now the question asks us to print k lines, where k is the number of distinct integers, where ith line contain the integer whose hash is (i-1)
But you can see by running above testcase that there is NO integer whose hash value is 1 so how can we print the second line.

So HASH function is wrong.

THE SOLUTION
What the question wants us to do is
Maintain a variable count = 0;
loop through the array and assign an element (at index i) the hash = count, when this element does NOT repeat after this index (index i) and increment count.

int hash[MAX + 1];
int count = 0;
for(int i = 0; i < n; i++) {
    if(ThisElementDoesNotRepeatAfterThisIndex(A, n, i)) {
    hash[A[i]] = count;
    count++;
    }
}

Here is the code

Mike and Hashtrick probem