Function to count same numbers in array C++

Question

I have this function that is supposed to count how many duplicates of same number occur in certain array. Important this must be of complexity O(logn). I wrote this one below, but it doesn't count the duplicates properly. Also one more thing, the numbers are sorted from lowest to highest.

int CountElementsinFile(int *Arr, int num, int numOfD)
{
    int avg{}; 
    int inB = 0; 
    int inE = numOfD - 1; 
    int el{};
    while (inB <= inE)
    {
        avg = (inB + inE) / 2;

        if (Arr[avg] == num)
            el++;
            if (Arr[avg] > num)
                inE = avg - 1;
            else
                inB = avg + 1;
    }

    return el;
}

Can you provide the input values and also show the results and desired results? — CodeLikeBeaker
– CodeLikeBeaker, Commented Mar 13, 2019 at 12:45
Is the array sorted? I'm not sure how you could find all duplicates in less then O(N) — NathanOliver
– NathanOliver, Commented Mar 13, 2019 at 12:45
to find duplicates you need to touch every element at least once, O(logn) is not possible — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Mar 13, 2019 at 12:50
You need to determine the upper and lower boundaries of num subsequence using the dichotomy method. The difference of this values is subsequence length. Your implementation of the dichotomy method is incorrect. — Dmytro Dadyka
– Dmytro Dadyka, Commented Mar 13, 2019 at 12:57

Jarod42 · Accepted Answer · 2019-03-13 13:01:08Z

2

With std, you might do:

int CountElementsinFile(const int *a, int size, int value)
{
    const auto range = std::equal_range(a, a + size, value);
    return range.second - range.first;
}

answered Mar 13, 2019 at 13:01

Jarod42

227k15 gold badges214 silver badges350 bronze badges

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

1 Comment

Lightness Races in Orbit Over a year ago

While true and a good solution for the real world, it seems clear that the OP is supposed to design the algorithm not just use an existing implementation.

Dmytro Dadyka · Accepted Answer · 2019-03-13 15:24:59Z

2

You need to determine the upper and lower boundaries of num subsequence using the Bisection method. You need to rearrange the lower or upper (depending on the comparison) search region boundary in the while loop until inB < inE reducing the region in half. The complexity will be O(ln(n)). You were close, but you will not be able to find both boundaries in one while loop. I just corrected your code.

int CountElementsinFile(int *Arr, int num, int numOfD)
{
   // There is no num in the array
   if (Arr[0] > num || Arr[numOfD - 1] < num)
      return 0;

   int avg{};
   int lb, ub;

   // Find lower boundary
   int inB = 0;
   int inE = numOfD - 1;
   while (inB < inE)
   {
      // divide search region
      avg = (inB + inE) / 2;
      if (Arr[avg] >= num)
         inE = avg;
      else
         inB = avg+1;
   }

   lb = inE;

   // Find upper boundary   
   // inB already found
   inE = numOfD - 1;
   while (inB < inE)
   {
      avg = (inB + inE + 1) / 2;
      if (Arr[avg] > num)
         inE = avg-1;
      else
         inB = avg;
   }

   ub = inB;

   return ub - lb + 1;
}

int main()
{
   int arr[] = { 5, 7, 8, 9, 9, 9, 9, 9, 11 };
   std::cout << CountElementsinFile(arr, 9, sizeof(arr) / sizeof(int)) << std::endl;
   return 0;
}

edited Mar 13, 2019 at 15:24

answered Mar 13, 2019 at 14:26

Dmytro Dadyka

2,2685 gold badges22 silver badges38 bronze badges

1 Comment

Jarod42 Over a year ago

split the method makes sense, and would make code clearer.

Botje · Accepted Answer · 2019-03-13 13:11:35Z

0

From the function signature you gave, I am guessing you were given a number N and a sorted array of numbers and need to count how many times N appears in the array.

Since the array is sorted, you need to find the index (using binary search) of the first number that is smaller than N (this is O(log n)), the index of the first number larger than N (this is also O(log n)), and simply substract one index from the other. Of course you need to take into account edge cases where there are no numbers smaller than N or larger than N, but that is for you to figure out.

edited Mar 13, 2019 at 13:11

answered Mar 13, 2019 at 12:59

Botje

32.2k4 gold badges36 silver badges47 bronze badges

1 Comment

Jarod42 Over a year ago

standard with algorithm comes with std::lower_bound/std::upper_bound for that.and std::equal_range when both are required.

poojakz · Accepted Answer · 2019-03-13 15:06:45Z

0

#include<algorithm>
using namespace std;

int CountElementsinFile(int arr[], int size, int numToSearch)
{
    return count(arr, arr + size, numToSearch); 
}

answered Mar 13, 2019 at 15:06

poojakz

477 bronze badges

1 Comment

Jarod42 Over a year ago

You are in linear complexity. whereas arr is sorted, we might have better complexity.

Collectives™ on Stack Overflow

Function to count same numbers in array C++

4 Answers 4

1 Comment

1 Comment

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

1 Comment

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related