Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

O(n^2) vs O(n) Techniques for Finding the Max Count of a Digit in the Given Numerical String

DZone's Guide to

O(n^2) vs O(n) Techniques for Finding the Max Count of a Digit in the Given Numerical String

Let's look at a couple of techniques for finding the max count of a certain digit in a string and see how complex or simple our solutions are.

· Performance Zone ·
Free Resource

Sensu is an open source monitoring event pipeline. Try it today.

Hello, Buddies. I came across this question related to Java String handling, so I thought of sharing it .

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

For a complete solution, refer to the Answer:

The first approach is 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? A solution with O(n) complexity, i.e. having a lookup array.

Answer: 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.

Happy coding! Check out the repo at this link.

Sensu: workflow automation for monitoring. Learn more—download the whitepaper.

Topics:
performance ,java ,arrays ,tutorial

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}