CODEWITHSUNDEEP
c++algorithm
grizzleKat456
grizzleKat456

Reputation: 127

Appears K times in an array C++

So I have an algorithm that is suppose to return the int that appears K times in an array. If more than 1 int appears K times, the higher value should be returned. My following algorithm is not working correctly. In the example below, it returns 1 when it should be returning 5. 

#include <iostream>
#include <algorithm>

int appearsKTimes (int size, int inputArray[], int k) {

    std::sort(inputArray, inputArray + size);
    int i = 1, count = 1;
    int element = inputArray[0];
    int res = -1;
    while (i < size) {
        if (element == inputArray[i]) {
            count++;
        } else {
            if (count == k) {
                res = element;
            }

            element = inputArray[i];
            count = 1;
        }
        i++;
    }
    std::cout << res << std::endl;
    return res;
}

int main() { 

    const int size = 7;
    int array[size] = {1, 1, 2, 2, 2, 5, 5};
    int occurences = 2;

    appearsKTimes(size, array, occurences);
}

Upvotes: 0

Views: 311

Answers (2)

gimme_danger
gimme_danger

Reputation: 798

Your approach with sorting is good and requires only O(NlogN) time complexity, but consider an another one with hash table as well. It requires O(N) in time and O(N) in space. It is shorter and has only a few extra variables, so there is less chance of making mistake:

1) Compute number frequencies with unordered_map (hash table): O(N)

2) Find the largest number with exactly k occurences: O(N)

int appearsKTimes (int size, int inputArray[], int k) {

    unordered_map<int, int> freqs;
    for (int i = 0; i < size; i++) {
        freqs[inputArray[i]]++;
    }

    int res = - 1;
    for (int i = 0; i < size; i++) {
        if (freqs[inputArray[i]] == k)
            res = max(res, inputArray[i]);
    }

    return res;
}

Upvotes: 1

liuyulvv
liuyulvv

Reputation: 174

if (count == k) {
    res = element;
}
std::cout << res << std::endl;

check the count of the last element.

I also think it will be better to count from the end.You need to check the all array all the time if you count from the first element.

Upvotes: 1

Related Questions