# Find out max duplicate number between 1 to N numbers

How can I make this method better?

int[] _input = new int[] { 5,45,184,594,14,8,5,184,1841,184,594,5,78,594,14,8,18,4,18,14,8,594};

Dictionary<int, int> _inputDictionary = new Dictionary<int, int>();

foreach (int i in _input)
{
if (_inputDictionary.ContainsKey(i))
{

_inputDictionary[i] = ++_inputDictionary[i] ;

}
else
{
}
}

Console.WriteLine();
Console.WriteLine("Maximum number repeated is " + _inputDictionary.OrderByDescending(g => g.Value).First().Key + " and it is repeated " + _inputDictionary.OrderByDescending(g => g.Value).First().Value+" times");


You can use GroupBy to count the duplicates.

Then you should sort the result and get the first item once, instead of sorting it each time you use it:

int[] _input = new int[] {
5, 45, 184, 594, 14, 8, 5, 184, 1841, 184, 594, 5, 78, 594, 14, 8, 18, 4, 18, 14, 8, 594
};

IGrouping<int, int> max =
_input.GroupBy(n => n)
.OrderByDescending(g => g.Count())
.First();

Console.WriteLine(
"Maximum number repeated is " + max.Key +
" and it is repeated " + max.Count() + " times"
);

• Thanks for that.could you explain me how does that linq work internally ?what would be the algorithmic complexity of both of our solutions??I am looking at this problem from interview purpose :) Sep 14, 2014 at 5:14
• @kyle: The GroupBy works basically as your use of the dictionary in the original code, so the complexity for that part is O(n). The compexity of a sort is typically O(n log n), but you could improve that to O(n) using a loop instead, as you only need the first item. Sep 15, 2014 at 18:18

I myself am still learning how to be a good citizen of CR (and reviewing helps me to understand the reviewers). I recommend reading this meta post.

For me it was at first reading hard to understand this line:

           _inputDictionary[i] = ++_inputDictionary[i] ;


And why you use Dictionary instead of HashSet, but got the idea from the printout:

   Console.WriteLine("Maximum number repeated is " + _inputDictionary.OrderByDescending(g => g.Value).First().Key + " and it is repeated " + _inputDictionary.OrderByDescending(g => g.Value).First().Value+" times")


Which would better be splitted to few more lines to make it more readable, e.g. like this:

Console.WriteLine("Maximum number repeated is "
+ _inputDictionary.OrderByDescending(g => g.Value).First().Key
+ " and it is repeated " + _inputDictionary
.OrderByDescending(g => g.Value).First().Value
+ " times");


Now I understand the purpose of the program - to actually count the duplicit values - you should probably describe your intent first stating this at the top.

...and we can look again at the strange line of code:

           _inputDictionary[i] = ++_inputDictionary[i] ;


I was at first thinking what is that? After reading the whole code, I got it - we have to store the incremented value back. I think that it would be better this way:

           _inputDictionary[i] = _inputDictionary[i] + 1;


Using HashSet with classes that contain both the value and the counter could make the code look more readable, but may impact the speed on the other way. I hope somebody else will address this.

• You don't need to store the value back when you are using the ++ operator. Just _inputDictionary[i]++; will do. Sep 13, 2014 at 18:34
• That was a part I was not completely sure about - that it works in C# (not returning reference as in C++). Will it call the setter automatically? I hope so.
– user52292
Sep 13, 2014 at 18:43
• In C# there isn't a separate ++ operator, it is implemented using the + operator. So _inputDictionary[i]++; is implemented as _inputDictionary[i] = _inputDictionary[i] + 1;, so it will write the value back to the dictionary. Sep 13, 2014 at 18:50
• Sep 13, 2014 at 22:46
• @radarbob: This is more about properties and how they work. ++ gets translated to +=1 which gets translated to set(get()+1).
– user52292
Sep 15, 2014 at 20:05

You don't need the sort at the end. Your algorithm should run in O(n) instead of O(nlgn). You can maintain the maximum duplicate encountered so far in a local variable as you only need the maximum, not the sorted array.

int[] _input = new int[] { 5, 45, 184, 594, 14, 8, 5, 184, 1841, 184, 594, 5, 78, 594, 14, 8, 18, 4, 18, 14, 8, 594 };

Dictionary<int, int> _inputDictionary = new Dictionary<int, int>();
int maxSoFar = int.MinValue;

foreach (int i in _input)
{
if (_inputDictionary.ContainsKey(i))
{

_inputDictionary[i] = ++_inputDictionary[i];
if (i > maxSoFar)
maxSoFar = i;
}
else
{
}
}

Console.WriteLine();
Console.WriteLine("Maximum number repeated is " + maxSoFar + " and it is repeated " + _inputDictionary[maxSoFar] + " times");


Firstly, it's recommended that when defining variables, if it's obvious what type the variable is from the right-hand-side, use var on the left. This way if you go to change the type later, you only have to change it in one place.

e.g

var _inputDictionary = new Dictionary<int,int>();


Additionally, it's also recommended not to use the variable's type in its name, or prefix with underscores.

var duplicateCounts = new Dictionary<int,int>();


Additionally, I think you can simplify your final statement using LINQ's Max function to:

int mostDuplicates = duplicateCounts.Keys.Max()
int valueWithMostDuplicates = duplicateCounts[mostDuplicates];

Console.WriteLine(String.Format("Maximum number repeated is {0} and it is repeated {1} times",
valueWithMostDuplicates,
mostDuplicates));