Thursday, 14 June 2018

O(n^2) vs O(n) techniques for finding the max count of a digit in the given numerical String.


Hello Buddies

Came across this question related Java String handling, so thought of sharing.

Question:
Given a string made up of n number of digits, find the digit having the maximum number of occurrence.
Eg. "12333123654"
Here, 3 is the digit being repeated for the maximum number of times.

Answer:
First approach can be to scan the string as a character array, maintain a map that can update the occurrence count. In the end find the max value and then the corresponding key.


Question:
What is the complexity of this solution?

Answer:
O(n^2) since we are iterating and using contains check.


Question:
Any better approach?

Answer:
Solution with O(n) complexity, i.e. having a lookup array.
We have digits 0 to 9, which can be related to each index of an array. For the values, update the occurrence count in the values.

For complete solution, refer to this link.

Happy Coding!!


Featured post

JAVA based project, that can be used to hit DB using JDBC, from WSO2 ESB

Hi Buddies, Here is a small project that will enable you to hit MySQL DB using WSO2 ESB - https://github.com/namitsharma99/customM...

Popular Posts