Skip to content

Instantly share code, notes, and snippets.

@schauhan232
Last active July 15, 2021 09:45
Show Gist options
  • Save schauhan232/1b8c26c91ee31f4d41533d586760f140 to your computer and use it in GitHub Desktop.
Save schauhan232/1b8c26c91ee31f4d41533d586760f140 to your computer and use it in GitHub Desktop.
C# Count frequncies of elements in array
Array of length n having integers 1 to n with some elements being repeated.
Count frequencies of all elements from 1 to n in Time Complexity O(n) and Space Complexity O(1)
class Program
{
public static void Main(string[] args)
{
var matrix = new int[] { 5, 2, 7, 7, 5, 5, 2 };
var someUniqueNumberGreaterThan = matrix.Max() + 1;
for (int i = 0; i < matrix.Length; i++)
{
matrix[i]--;
}
for (int i = 0; i < matrix.Length; i++)
{
var value = matrix[i];
var originalValue = -1;
if (value > someUniqueNumberGreaterThan)
{
originalValue = matrix[i] % someUniqueNumberGreaterThan;
}
if (originalValue != -1)
{
matrix[originalValue] = matrix[originalValue] + someUniqueNumberGreaterThan;
}
else
{
matrix[value] = matrix[value] + someUniqueNumberGreaterThan;
}
}
for (int i = 0; i < matrix.Length; i++)
{
Console.WriteLine($"{i + 1} : {matrix[i]/ someUniqueNumberGreaterThan}");
}
Console.Read();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment