Why doesn't my code work for this problem?

Question

They are given in natural numbers. List the digits that appear in the decimal notation of these numbers in ascending order of occurrence. If two digits have the same number of occurrences, the smaller digit will be displayed first.

The Example:

In

5 124 229 1322 4 534

Out

5 9 1 3 4 2

This is my code:

#include <iostream>

using namespace std;

int v1[10],v2[10],lim,x,ok;

int main()
{
    cin>>lim;

    for(int i=1; i<=lim; i++)
    {
        cin>>x;

        while (x>0)
        {
            v1[x&10]++;
            v2[x%10]=x%10;
            x=x/10;
        }
    }
    while (!ok)
    {
        ok=1;

        for(int i=0; i<=lim; i++)
        {
            if(v1[i]>v1[i+1])
            {
                swap (v1[i],v1[i+1]);
                swap (v2[i],v2[i+1]);
                ok=0;
            }
        }
    }
    ok=0;
    while (!ok)
    {
        ok=1;

        for(int i=0; i<lim; i++)
        {
            if(v2[i]>v2[i+1])
                if(v1[i]==v1[i+1])
                    swap (v2[i],v2[i+1]);
        }
    }
    for (int i=0; i<=10; i++)
    {
        if(v2[i]!=0)
            cout<<v2[i]<<" ";
    }
}

It won't sort the way I want

I've tried to sort it 2 times

why does output start with `5 9` ? `5` occurs twice and `9` only once — 463035818_is_not_an_ai, Mar 17 '23 at 12:29
@463035818_is_not_a_number The first 5 is the number of inputs and doesn't count. — molbdnilo, Mar 17 '23 at 12:43
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Mar 17 '23 at 14:29

score 1 · Answer 1 · answered Mar 17 '23 at 12:23

You should increment v1[x%10] (using modulo), not v1[x&10] (using bitwise AND)
The two sorting should be done for the 10 elements of v1 and v2, not lim+2 nor lim+1 elements.
v2[10] is out-of-range, so you mustn't access that.

Fixed code:

#include <iostream>

using namespace std;

int v1[10],v2[10],lim,x,ok;

int main()
{
    cin>>lim;

    for(int i=1; i<=lim; i++)
    {
        cin>>x;

        while (x>0)
        {
            // use modulo instead of bitwise AND
            //v1[x&10]++;
            v1[x%10]++;
            v2[x%10]=x%10;
            x=x/10;
        }
    }
    while (!ok)
    {
        ok=1;

        // sort 10 elements instead of lim+2
        //for(int i=0; i<=lim; i++)
        for(int i=0; i<9; i++)
        {
            if(v1[i]>v1[i+1])
            {
                swap (v1[i],v1[i+1]);
                swap (v2[i],v2[i+1]);
                ok=0;
            }
        }
    }
    ok=0;
    while (!ok)
    {
        ok=1;

        // sort 10 elements instead of lim+1
        //for(int i=0; i<lim; i++)
        for(int i=0; i<9; i++)
        {
            if(v2[i]>v2[i+1])
                if(v1[i]==v1[i+1])
                    swap (v2[i],v2[i+1]);
        }
    }
    // deal with the 10 elements instead of 11
    //for (int i=0; i<=10; i++)
    for (int i=0; i<10; i++)
    {
        if(v2[i]!=0)
            cout<<v2[i]<<" ";
    }
}

Actually the second sort can be removed because you are using bubble sort, which is stable, and the numbers in v2 are already in increasing order before the first sorting.

Also note that your program won't print 0 even when it is in the input like 5 120 34 56 78 90. If you want to include 0 in the output, you should use if(v1[i]!=0) instead of if(v2[i]!=0). Even with this change, this program won't work when zero or negative numbers are in the input.

score 0 · Answer 2 · answered Mar 17 '23 at 13:05

The deeper reason your code produces wrong output is that it is too complicated. Just to name the major complication factors:

Using cryptic variable names is making the code harder to read. Hard to read code is more likely to have bugs.

You implement it all from scratch rather than using existing algorithms. Code that manually implements algorithms rather than using facilities from the standard library is more likely to have bugs.

C-arrays have quirks and are complicated. Perhaps most importantly they require you to keep track of their size seperately (actually the size is readily available, because its part of the type, but thats cumbersome). Code that uses c-arrays rather than standard containers is more likely to have bugs.

As you need to deal with single digits only, it is simpler to read the input as string. To count number of occurences you can use a std::map.

std::map<char,unsigned> counts;
for (int i=0;i<n;++i) {
    std::string number;
    std::cin >> number;
    for (char digit : number) ++counts[digit];
}

counts has all digits as keys and their occurences as mapped values. It is sorted with respect to digits (note that an unordered_map would do as well, anyhow the order is not yet the desired one).

To sort it with respect to occurences we populate a map that has occurences as keys and digits as mapped values. Because two different digits cabn have the same number of occurences and because the output the smaller digits should appear first, we can use a set<char> to store the digits:

std::map<unsigned,std::set<char>> digits;
for (const auto& elem : counts) {
    digits[elem.second].insert(elem.first);
}

The output is now just a nested loop to iterate all occurences and for each occurence the digits present in the set:

for (const auto& elem : digits) {
    for (const auto& digit : elem.second) {
        std::cout << digit << " ";
    }
}

Thats really all that is needed. The only piece I left out from the code is reading the value of n. You only have to add the pieces together.

lastchance · Answer 3 · 2023-03-17T14:28:15.280

The model answer (5 9 1 3 4 2) appears to be wrong for the given test case (5 124 229 1322 4 534).

You could work almost entirely in terms of chars if you wanted to: they have the same ordering as digits. Making heavy use of standard library routines like stable_sort:

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

int main()
{
   string test = "5 124 229 1322 4 534";
   int freq[10]{};
   for ( char c : test ) if ( isdigit( c ) ) freq[c-'0']++;
   string digits = "0123456789";
   stable_sort( digits.begin(), digits.end(), [&freq]( char a, char b ){ return freq[a-'0'] < freq[b-'0']; } );
   for ( char c : digits ) if ( freq[c-'0'] ) cout << c << ' ';
}

9 1 3 5 4 2

Why doesn't my code work for this problem?

3 Answers3