count frequencies of all elements in array without using another array or changing the elements of the given array

Question

Hello so the catch of this problem is you shouldn't use another array or function and do not change the elements of the given array or sort them and we don't know the interval of the elements and side note i shouldn't show the numbers twice

for example if we have a[10]={1,2,1,3,1,5,2,4,3,1} it should print out :

1 --- 4

2 --- 2

3 --- 2

4 --- 1

5 --- 1

I wrote a code for finding the repeating numbers using two for loops but i dont know how to stop it from repeating the same answer and how to make it show the counter

here is the code:

#include<iostream>
using namespace std;

int main()
{
    int arr[5];
    int size = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < 5; i++)
    {
        cout << "Enter " << i << " number:";
        cin >> arr[i];
    }
    {
        for (int i = 0; i < size; i++)
            for (int j = i + 1; j < size; j++)
                if (arr[i] == arr[j])
                    cout << " Repeating elements are " << arr[i] << " " << endl;
    }
    return 0;
}

Answer 1

See the code below.

I made the array a constant for brevity. You can just copy-paste in your code that reads it from the user input.

The trick is to check for each i that this is the first time that a[i] is found. If it has been found before, then it has already been counted on that previous iteration, and can be skipped now.

#include <iostream>
using namespace std;

int main()
{
    const int a[]={1,2,1,3,1,5,2,4,3,1};
    const int size = sizeof(a) / sizeof(a[0]);

    for (int i = 0; i < size; i++)
    {
        bool duplicate = false;
        for (int j = 0; j < i; j++)
        {
            if (a[i] == a[j])
            {
                duplicate = true;
                break;
            }
        }
        if (duplicate)
        {
            continue;
        }
        int count = 1;
        for (int j = i + 1; j < size; j++)
        {
            if (a[i] == a[j])
            {
                count++;
            }
        }
        cout << a[i] << " -- " << count << '\n';
    }
}

Answer 2

Logic:

As you said there won't be negative numbers, I am making the duplicate values negative of the current value (to memorize that it's a duplicate value) and whenever I encounter a negative value I then make it simply positive (to get back to the original array).

#include <iostream>

int main()
{
    int arr[10] = {1,2,1,3,1,5,2,4,3,1}, cnt = 0, size = 10;

    for (int i = 0; i < size; i++) {
      cnt  = 1;

      if (arr[i] < 0) {
        arr[i] = -arr[i];
        continue;
      }

      for (int j = i + 1; j < size; j++) {

          if (arr[i] == arr[j]) {
            arr[j] = -arr[i];
            cnt++;
          }
        }

        std::cout <<  arr[i] << " " << cnt << '\n';
      }

    return 0;
}

output:

1 4
2 2
3 2
5 1
4 1

Note:

If changing the values in the array is allowed, making sure we will be left with the original array at the end of the program.

Answer 3

Maintain the previous smallest and look for the next smallest element in the array. Then run a loop to count it and set previous smallest to current smallest.

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int N;
    cin >> N;
    vector<int> V(N);
    for (int& e : V)
        cin >> e;

    int prev_smallest = numeric_limits<int>::min();
    int smallest = numeric_limits<int>::max();
    for (int c = 0; c < N; )
    {
        for (int j = 0; j < V.size(); ++j)
            if (prev_smallest < V[j] && V[j] < smallest)
                smallest = V[j];

        int count = 0;
        for (int j = 0; j < V.size(); ++j)
            if (V[j] == smallest)
                ++count;
        cout << smallest << ' ' << count << endl;
        prev_smallest = smallest;
        smallest = numeric_limits<int>::max();
        c += count;
    }
}

Answer 4

This routine makes one pass along the array for each value counted plus one initial pass to identify the minimum and maximum value to count. Additionally, it prints values in an increasing order.

The for(;;) {} trick is equivalent to while(true) {}, that is 'iterate forever'. The loop does not actually work forever, because it breaks iterations in the last if().

void printCounts()
{
    const int a[]={1,2,1,3,1,5,2,4,3,1};
    const int size = sizeof a / sizeof a[0];

    int currentValue = a[0];
    int maxValue     = a[0];

    // find the first (minimum) and the last (maximum) value to count

    for (int i = 1; i < size; i++)
    {
        if (a[i] < currentValue)
            currentValue = a[i];
        if (a[i] > maxValue)
            maxValue = a[i];
    }

    // count items equal current value,
    // identify a next value to count,
    // print result,
    // reiterate
    for (;;)
    {
        int count = 0;
        int nextValue = maxValue;

        for (int i = 0; i < size; i++)
        {
            if (a[i] == currentValue)
                count ++;
            if (a[i] > currentValue && a[i] < nextValue)
                nextValue = a[i];
        }

        std::cout << "value:" << currentValue << "  count:" << count << std::endl;

        // all values counted ?
        if (currentValue == maxValue)
            break;

        // count nextValue
        currentValue = nextValue;
    }
}

Verified with GDB online Debugger. Results were:

value:1  count:4
value:2  count:2
value:3  count:2
value:4  count:1
value:5  count:1

Answer 5

Of course you could do the task very easy if you were allowed to use standard containers as for example std::map.

Here is a demonstration program.

#include <iostream>
#include <map>

int main() 
{
    int a[] = { 1, 2, 1, 3, 1, 5, 2, 4, 3, 1 };
    std::map<int, size_t> m;
    
    for ( const auto &item : a )
    {
        ++m[item];
    }

    for ( const auto &item : m )
    {
        std::cout << item.first << " --- " << item.second << '\n';
    }

    return 0;
}

The program output is

1 --- 4
2 --- 2
3 --- 2
4 --- 1
5 --- 1

If you are not allowed to use any standard container and may not change the array in any way and the output shall be sorted according to the values stored in the array then you can use the following (though inefficient) approach using only loops.

Here is another demonstration program.

#include <iostream>

int main() 
{
    int a[] = { 1, 2, 1, 3, 1, 5, 2, 4, 3, 1 };
     
    const size_t N = sizeof( a ) / sizeof( *a );
     
    int value;
    
    for ( size_t n = 0; n != N; )
    {
        size_t i = 0;
        
        if ( n != 0 )
        {
            while ( ( i != N ) && !( value < a[i] ) ) ++i;
        }

        size_t count = 1;
        size_t min_i = i;
        
        while ( ++i != N )
        {
            if ( ( a[i] < a[min_i] ) && ( n == 0 || value < a[i] ) )
            {
                min_i = i;
                count = 1;
            }
            else if ( a[min_i] == a[i] )
            {
                ++count;
            }
        }

        value = a[min_i];
        std::cout << value << " --- " << count << '\n';
        
        n += count;
    }
     
    return 0;
} 

The program output is the same as shown above.

1 --- 4
2 --- 2
3 --- 2
4 --- 1
5 --- 1