# Count frequencies of array elements in range 1 to n

Given an array of length n having integers 1 to n with some elements being repeated. Count frequencies of all elements from 1 to n.
Example:
Input Array: {2, 3, 3, 2, 5}
Output:
1 0
2 2
3 2
4 0
5 1

Amazon, Goldman Sachs

## Algorithm/Insights

Algorithm 1: O(n^2) time and O(1) space
Use 2 loops.
1. Outer loop runs from i = 1 to n.
2. Inner loop calculates the count of i in the input array.
3. Print the count of i when inner loop ends.

Algorithm 2: O(n) time and O(n) space
1. Create a count array of size n with all elements from index i = 0 to n-1 initialized to 0.
Here, count[i] is count of i+1.
2. Traverse the array once. For i = 0 to n-1, increment count[input[i]-1] by 1.
3. Traverse count array and print count array.

Algorithm 3: O(n) time and O(1) space
1. Reduce all elements by 1 so that the elements are converted in the range 0 to n-1.
2. Traverse the input array and for i = 0 to n-1, add n to element at index (input[i]%n). After all the elements are completed, element at index i will be increment by n*k where k is the number of times i occurs in the array.
3. Finally, print counts of elements. Count of i+1 will be input[i]/n.
Reason:
Element at index i will be equal to input[i] + n*k where k is the number of times i occurs in the array.
On dividing by n, we get: (input[i] + n*k)/n = input[i]/n + (n*k)/n = 0 + k = k = the number of times i occurs in the array
As initially, all elements were reduced by 1, so this is count of i+1.
4. Traverse input array once and set input[i] = input[i]%n+1 to get original array.

Example:
Input Array: [2, 3, 3, 2, 5]
n: 5
After step #1, array will be:
[1, 2, 2, 1, 4]
Step #2:
i = 0: Set input[input%5] = input[input%5] + 5
= input[1%5] + 5
= input + 5
= 2 + 5
= 7
Array: [1, 7, 2, 1, 4]

i = 1: Set input[input%5] = input[input%5] + 5
= input[7%5] + 5
= input + 5
= 2 + 5
= 7
Array: [1, 7, 7, 1, 4]

i = 2: Set input[input%5] = input[input%5] + 5
= input[7%5] + 5
= input + 5
= 7 + 5
= 12
Array: [1, 7, 12, 1, 4]

i = 3: Set input[input%5] = input[input%5] + 5
= input[1%5] + 5
= input + 5
= 7 + 5
= 12
Array: [1, 12, 12, 1, 4]

i = 4: Set input[input%5] = input[input%5] + 5
= input[4%5] + 5
= input + 5
= 4 + 5
= 9
Array: [1, 12, 12, 1, 9]

After step #2: Input Array = [1, 12, 12, 1, 9]

Step #3: Print all elements:
(i+1)   input[i]/n
1        0
2        2
3        2
4        0
5        1

Step #4: Get back original array by setting input[i] = input[i]%n+1
i = 0: Set input = input%5+1
= 1%5+1
= 1 + 1
= 2
i = 1: Set input = input%5+1
= 12%5+1
= 2 + 1
= 3
i = 2: Set input = input%5+1
= 12%5+1
= 2 + 1
= 3
i = 3: Set input = input%5+1
= 1%5+1
= 1 + 1
= 2
i = 4: Set input = input%5+1
= 4%5+1
= 4 + 1
= 5
Hence original array is obtained as [2, 3, 3, 2, 5]

Code for all the 3 algorithms is given in code snippet section.

## Code Snippet

```
package com.ideserve.questions.saurabh;

/**
* <b>IDeserve <br>
* Given an array of length n having integers 1 to n with some elements being repeated.
* Count frequencies of all elements from 1 to n.
*
* @author Saurabh
*/
public class CountFrequencies {

// O(n^2) time and O(1) space
public static void countFrequenciesNaive(int[] input) {
int n = input.length;
for (int i = 1; i <= n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (input[j] == i) {
count++;
}
}
System.out.println(i + " " + count);
}
}

// O(n) time and O(n) space
public static void countFrequencies(int[] input) {
int n = input.length;
int[] count = new int[n];

for (int i = 0; i < n; i++) {
count[i] = 0;
}

for (int i = 0; i < n; i++) {
count[input[i] - 1]++;
}

for (int i = 0; i < n; i++) {
System.out.println(i + 1 + " " + count[i]);
}
}

// O(n) time and O(1) space
public static void countfrequenciesEfficient(int input[]) {

int n = input.length;
for (int i = 0; i < n; i++) {
input[i]--;
}

for (int i = 0; i < n; i++) {
input[input[i] % n] += n;
}

for (int i = 0; i < n; i++) {
System.out.println((i + 1) + " " + input[i] / n);
// Change the element back to original value
input[i] = input[i] % n + 1;
}
}

public static void main(String[] args) {
int[] input = { 2, 3, 3, 2, 5 };
countfrequenciesEfficient(input);
}
}
```

## Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)