All Tracks Data Structures Hash Tables Basics of Hash Tables Problem

The Monk and Prateek
Tag(s):

Easy-Medium, Easy-Medium, Hashing, Implementation

Problem
Editorial
Analytics

The Monk is extremely fond of Prateek, the new HackerEarth moderator. This time, Prateek had to deal with a crazy hash function, $$f(n)$$, called the r3gz3n function, which is as follows: $$N$$ xor $$(sum \; of \; digits \; of \; N)$$. For example, $$f(81)$$ = $$81$$ ^ ($$8$$+$$1$$) = $$88$$.

Now to test the efficiency of his friend, The Monk gives Prateek a list of N numbers, and asks him to find out the following information about this list:

  • The value of the r3gz3n function which occurs the maximum number of times.
  • Number of collisions with the hash function.

Note-1: If all the values of the function are unique, print the maximum value which occurs in the list of the hashed values.
Note-2: If there are multiple hashed values which occur the maximum number of times, print the smallest hashed value with the maximum count.

Input format:
The first line will contain a single digit integer, N, denoting the number of numbers in a list. The second line will contain N integers, each separated by a space.

Output format:
Print two integers separated by a space, where the first integer denotes the value of the function which occurs the maximum number of times. Remember that if all the values of the function are unique, print the maximum value which occurs in the list. The second integer would denote the number of collisions.

Constraints:
$$1$$ ≤ N ≤ $$10^5$$
$$1$$ ≤ Ni ≤ $$10^7$$

Sample Input-0:
$$4$$
$$10$$ $$11$$ $$12$$ $$13$$

Sample Output-0:
$$9$$ $$1$$

Sample Explanation-0:
$$10$$^$$1$$ = $$11$$.
$$11$$^$$2$$ = $$9$$.
$$12$$^$$3$$ = $$15$$.
$$13$$^$$4$$ = $$9$$.

The value which occurs the maximum number of times is: $$9$$, and the number of collisions is: $$1$$.

Sample Input-1:
$$4$$
$$1$$ $$1$$ $$21$$ $$21$$

Sample Output-1:
$$0$$ $$2$$

Sample Explanation-1:
$$1$$^$$1$$ = $$0$$.
$$1$$^$$1$$ = $$0$$.
$$21$$^$$3$$ = $$22$$.
$$21$$^$$3$$ = $$22$$.

The value which occurs the maximum number of times: $$0$$, and $$22$$; but since $$0$$ is the smaller one, that is our answer.The number of collisions are: $$2$$.

SAMPLE INPUT
2
40 50
SAMPLE OUTPUT
55 0
Explanation

As here, $$N=2$$

1) $$40$$^$$(4+0) = 44$$
2) $$50$$^$$(5+0) = 55$$

Here all the values are unique, so maximum value will be $$55$$ and number of collisions are $$0$$.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

Code Monk (Hashing)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications