992A. Nastya and an Array

Implementation

Nastya owns too many arrays now, so she wants to delete the least important of them. However, she discovered that this array is magic! Nastya now knows that the array has the following properties:

1. In one second we can add an arbitrary (possibly negative) integer to all elements of the array that are not equal to zero.
2. When all elements of the array become equal to zero, the array explodes.

Nastya is always busy, so she wants to explode the array as fast as possible. Compute the minimum time in which the array can be exploded.

Read the question with I/O specifications at codeforces.com.

Hints

1. Think of grouping same elements together.

Solution

This problem becomes complicated if we think of eliminating elements individually because each element need not necessarily be unique.

For easier understanding, imagine the array is sorted. So all the same elements are now grouped together. Now each group can be eliminated by adding the respective integer. That is the final the answer will be the number of groups which is the number of distinct non-zero integers.

To find number of distinct integers we can use an STL container like Set (In a Set only distinct elements are added). Hence the size of the Set will be the number of distinct elements.

Code

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long int n,k,i,j;

    //SET IN C++ CAN SORT AND CAN REMOVE DUPLICATE ELEMENTS
    set< long long int > s;

    cin >> n;
    for(i = 0;i < n;i++)
    {
        cin >> j;

        //IF ELEMENT IS NOT ZERO INSERT INTO SET
        if(j != 0)
            s.insert(j);
    }    

    //PRINTING THE NO.OF DISTINCT NON-ZERO INTEGERS
    cout << s.size() << endl;
    return 0;
}

Written by Manoj