PROBLEM LINK:
Author: Praveen Dhinwa
Tester 1 Goutham Kobakini
Tester 2 Arjun Arul
Editorialist: Praveen Dhinwa
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef wants to buy a laptop of lowest possible unique cost. It is guaranteed that there is a valid way of buying laptop. Find out minimum amount of money Chef needs. Let c denote the cost array.
QUICK EXPLANATION
We have to find smallest non-repeating element in the array c. I have explained following three ways in which you can solve the problem.
- Make an array cnt such that cnt[i] denotes number of occurrences of laptops having cost equal to i.
Now we can iterate over the cnt array and pick the first laptop such that cnt of that laptop is exactly one. - Sort the array, identify the least unique element. You can decide whether an element is unique or not by looking at previous and next elements to it in the sorted order.
- Using STL map, you can keep count of occurrences of a particular element in the array. This way, you can detect whether an element is unique or not.
EXPLANATION
Please note that I have used 1 based indexing during the entire editorial. It is only used for making the explanation more intuitive. You are advised to use 0 based indexing while writing the codes.
Algorithm for finding smallest non-repeating element in an array
If the minimum element of array is unique, then we can pick that up. Otherwise, we will check with next large element. Note that the condition “It is guaranteed that there is a valid way of buying laptop” makes sure that there is at least one unique element in the array.
Solving the problem by making a count array
There are many ways of implementing the above algorithm. As element of the array c lies between 1 to 100, we can make an array cnt of size > 100, which will store the count of number of occurrences of elements. eg. Here cnt[i] denotes number of occurrences of element i in the array c.
Pseudo Code
// create cnt array, Note that "= {0}" is used for initializing the cnt array by zeros.
int cnt[101] = {0};
for (int i = 1; i <= n; i++)
cnt[cost[i]]++;
int ans = 0;
for (int i = 1; i <= 100; i++)
if (cnt[i] == 1) {
ans = i;
break;
}
printf("%d\n", ans);
Time Complexity
As we are iterating over the array c only once. Then we are iterating over the cnt array once which will take at most \mathcal{O}(100) times. So overall time taken will be \mathcal{O}(n + 100).
As you know that n can be as large as 100. So we can even say that time complexity is \mathcal{O}(n) because normally we remove all the constant factors in the time complexity big O notation.
Possible bugs in its implementation
-
Declaring cnt array of size 100
If instead of writing array cnt of size 100, not of 101 (i.e. you write int cnt[100]). In this case, if the only unique element in the array is 100, then your code will try to access cnt[100]. So your code is trying to access an invalid/ unallocated memory. This falls in the category of undefined behaviour in C++. By undefined behaviour, we mean that your code can access the memory and can even give correct answer. It can also be not able to access the memory too which will lead to run time error(segmentation fault). It can even lead to wrong answer because you are able to read the memory, but memory contains some garbage values. So overall, it can lead to run time error or wrong answer. In Java, it will lead you to run time error (ArrayIndexOutOfBoundsException). -
Not using break statement in the loop.
In this case, your program will give wrong answer because it will pick the unique highest element instead of unique lowest element.
Take home points
So the take home point from this fault to make sure that you have allocated enough memory for the arrays. Also you should not declare array statically (i.e. inside functions).
Static declaration
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
int a[n]; // This is static declaration of array.
}
}
You should not use the above mentioned static declaration of array. Note that total memory declared by you is n * T. If n * T is large, then this code will get segmentation fault(run time error).
You can use dynamic allocation of the arrays too. Dynamic allocations of the array can be done using malloc() in C/C++.
You should ideally declare all the arrays globally. eg.
Global declaration
int a[100000 + 5]; // This is global declaration of array.
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n;
scanf("%d", &n);
}
}
Faster solution using sorting
Let sort the array c. Now we will iterate over the array from left to right. Also we need to check whether an element has occurred only once in the array c or not. As we know that array is sorted, so all the equal values will be contiguous in the array. So we can check uniqueness of this element by simply checking whether any of the previous or next element is equal to this element or not.
Pseudo Code
sort(c + 1, c + n + 1); // this is STL sort function, please check its documentation
int ans = 0;
for (int i = 1; i <= n; i++) {
int isUniqueElement = true;
// check whether this element is equal to previous or not.
if (i >= 2 && c[i] == c[i - 1]) isUniqueElement = false;
if (i < n && c[i] == c[i + 1]) isUniqueElement = false;
if (unique) {
ans = c[i];
break;
}
}
printf("%d\n", ans);
Time Complexity
For sorting, you can use standard \mathcal{O}(n^2) sorting algorithms or you can even use STL sorting which works in \mathcal{O}(n log n) time and has a very simple one line code as shown in previous section.
Possible bugs
- Accessing wrong memories while checking uniqueness condition.
eg. if (c[i] == c[i - 1]) isUniqueElement = false;
If you write this line, then at index i = 1, your code can go wrong as c[0] does not represent a valid element of the array(As we are assuming 1 based indexing). So we are accessing a wrong memory which might contain some undesired value.
Another way of counting occurrences of an element using STL map
Using STL map, you can count number of occurrences of a particular number. Complexity of adding, deleting, checking count of an element in a map is \mathcal{O}(n log n). Its implementation contains balanced binary search tree underneath.
Pseudo Code
map cnt;
int ans = 0;
for (int i = 1; i <= n; i++) {
cnt[c[i]]++;
}
sort(c + 1, c + n + 1);
for (int i = 1; i <= n; i++) {
if (cnt.count(i) == 1) {
ans = i;
break;
}
}
printf("%d\n", ans);
Time Complexity
As stated above, map in STL takes \mathcal{O}(n log n) time. So overall time taken will be in updating the cnt array will be \mathcal{O}(n log n). The remaining time is in sorting and an \mathcal{O}(n log n) loop again.
If you use \mathcal{O}(n log n) sorting, then time taken will be \mathcal{O}(n log n).