# CHEFLAPT- Editorial

Author: Praveen Dhinwa
Tester 1 Goutham Kobakini
Tester 2 Arjun Arul
Editorialist: Praveen Dhinwa

Cakewalk

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

• 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).