Count different element of an array

Question

I'm an IT stutend an we will have a programing exam where a test program will test our program. One of the particle examp is that we get ages and salaries of peoples, we have to count how many differet age people have

My code looks like this The struc:

struct input
{
    int emp_age, emp_paid;
};

And this is the code, n is represent the number of all people

int diff_sum (int n, input* t)
{
    int uniq_num = n;

    for(int i = 0; i < n; i++)
        {
            for(int j = i; j < n; j++)
                {
                    if((t[j].emp_age == t[i].emp_age) && (i!=j))
                        {
                            uniq_num = uniq_num - 1;
                        }
                }
        }
    cout << uniq_num << endl;
    return 0;
}

The program test 10 times, and some of said the out put is good but for some test it said it's wrong out put. I don't know how the test engine works, and i also dont know what the problem coud be.

What you should do first is show or log the input and get the specific input(s) that produce the incorrect result. Then you know where to begin looking. — dutt
– dutt, Commented Jan 6, 2014 at 16:12

BoBTFish · Accepted Answer · 2014-01-06 16:27:26Z

3

Consider this: 10 10 10. Think of i and j as pointing at elements:

uniq_num = 3
10 10 10
 i  j    => uniq_num = 2

10 10 10
 i     j => uniq_num = 1

10 10 10
    i  j => uniq_num = 0!!!!

So we see that in the second outer iteration, we compare two numbers that we already known are the same. They have already been indirectly compared.

Assuming you are not allowed to use any standard library facilities (if you are, why aren't you? This would be trivial with a std::set!), I would work in sort of the opposite order.

Start with unique=0.
Look at the first element. Increment count.
Look at the next element. Compare it with all the previous elements. If none match, increment count.
Repeat.

(Be aware that this isn't the best algorithm, and is not what I would do for large inputs, but it's pretty simple to explain and implement using the most basic C++ concepts.)

edited Jan 6, 2014 at 16:27

answered Jan 6, 2014 at 16:15

BoBTFish

19.8k3 gold badges54 silver badges78 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Sceptical Jule · Accepted Answer · 2014-01-06 16:22:55Z

1

One possibility would be to add all elements to an STL container with unique values:

int diff_sum (int n, input* t)
{
    std::set<int> ages;
    for(int i = 0; i < n; i++)
        ages.insert(t[i].emp_age);

    return ages.size();
}

answered Jan 6, 2014 at 16:22

Sceptical Jule

9171 gold badge10 silver badges26 bronze badges

2 Comments

BoBTFish Over a year ago

I think you mean std::set.

Sceptical Jule Over a year ago

Damn it. I did mean set just wrote list. Thanks.

barak manos · Accepted Answer · 2014-01-06 16:53:43Z

Algorithm:

Find the minimum and maximum ages (let's call them min_age and max_age)
Allocate an array with max_age-min_age+1 entries (let's call it age_arr)
Set all entries in age_arr to 0
For each structure x, set 1 in entry # x.emp_age-min_age
Sum all the values (0s or 1s) in age_arr, delete age_arr and return the result

Implementation:

//Phase 1
int min_age = 1000; // Assumption!!!
int max_age =    0; // Assumption!!!
for(int i=0; i<n; i++)
{
    if (min_age > t[i].emp_age)
        min_age = t[i].emp_age;
    if (max_age < t[i].emp_age)
        max_age = t[i].emp_age;
}

//Phase 2
int age_arr_size = max_age-min_age+1;
int age_arr[] = new int[age_arr_size];

//Phase 3
for(int age=0; age<age_arr_size; age++)
    age_arr[age] = 0;

//Phase 4
for(int i=0; i<n; i++)
    age_arr[t[i].emp_age-min_age] = 1;

//Phase 5
int age_count = 0;
for(int age=0; age<age_arr_size; age++)
    age_count += age_arr[age];
delete[] age_arr;
return age_count;

OliKlima · Accepted Answer · 2014-01-06 23:51:07Z

0

The problem is that your code will underestimate the number of unique ages:

e.g. say the ages are {1,2,3,4,1,5,6,1,7}

Clearly there are 7 unique ages here, and n = 9.

In your code, the only time uniq_num will get reduced is when i = 0 (when uniq_num is reduced by 2) and i = 4 (when uniq_num is reduced by another 1).

The latter case is double-counting, so your algorithm gives an answer of 6 instead of 7.

edited Jan 6, 2014 at 23:51

answered Jan 6, 2014 at 18:14

OliKlima

416 bronze badges

Collectives™ on Stack Overflow

Count different element of an array

4 Answers 4

Comments

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related