String digit occurence

[Mount eerie]

Hey guys. What is the best way of approaching creating a program that looks at a string of characters and digits and prints the most frequently occurring digit. Lets say my string consists of gh9k8k8k8. 8 would be the most frequently occurring digit so the program would simply output 3 since 8 occurred 3 times. Im not sure how I can go through every chracter and number in the string.

[Mount eerie]

Im guessing my first task would be to check each character in the string and figure out if thats a digit. I know I could use the isdigit function but what then after that?

[whitenite1]

You could first create an array of 10, for numbers 0 to 9, and initialize them to 0. When you go through the string and find a digit, increase the array position of that number, by one. When you're finished reading the string, loop through the array and find the position with the highest value, and that gives you the highest frequency.

[Mount eerie]

When you say initialize them to 0 how exactly do you mean.

So like arr[10] = {0,1,2,3,4,5,6,7,8,9}

what would I do with that after I create it.

Also lets say I take the approach to just simply use isdigit to check each character. How would I use a counter to count separately for each digit. For example : a44g9kl3. The output should be 2 since the most frequent digit being 4 occurs twice. But since their are multiple digits how can I have my counter count separately for each digit.

[whitenite1]

Now, when you loop through the string and use isdigit(), and find that is is, you increase that array location by one.

#include <iostream>
#include <ctype.h>

using namespace std;

int main()
{
	string check_me="gh9k8k8k8";
	int arr[10]={0};
	int len = check_me.length();
	int num;
	for(int x=0;x<len;x++)
	{
		if(isdigit(check_me[x]))
		{
			num = check_me[x] - '0'; // Gives num the value of the isdigit()
			arr[num]++; // Increases that array location, by 1
		}
	}
	for (int x=0;x<10;x++)
		cout << "arr["<<x<<"] = " << arr[x] << endl;
}

Now it's up to you to check which array location is the highest.

[Mount eerie]

Wow thats so simple I dont know why I didn't come up with using the array like that. Thanks so much man!

[whitenite1]

@edifarnecio

Wow thats so simple I dont know why I didn't come up with using the array like that.

I think that sometimes, people over-think for a solution. Me, I try the K.I.S.S. way.
(ie.. Keep It Simple Stupid)

And, you're welcome.

[jonnin]

another way to do the same thing without all the conversions to values work and checks.

int counts[256] = {0};
for(i = 0; i < var.length(); i++)
{
counts[var[i]]++;
}
for(i = '0'; i <= '9'; i++)
{
// find max of counts in this range. That (i) is your digit (as a char).
}

this is a common variation on what is called a bucket sort. Which basically makes a 'bucket' for every possible value in a list, and when you find it, you increment the bucket. O(N).. and then its 'sorted' because you can iterate the bucket and if its not zero, spew out the value... in sorted order. It only works on data in specific formats, but when it works, its a ton faster than the generic algorithms. Its good for 3 things commonly done.. sorting, counting, and compressing (via elimination of redundant values, though it can just as easily bloat if the list is small and the range is large).

[Mount eerie]

Awesome guys I really appreciate all your help program works beautifully and I didnt know about bucket sorting i've only learned the bubble sort method which is a bit tedious to code.

Anybody know why I get a warning about this line of code

int len = frequent.length();

Im not getting an error and the program runs but id rather get rid of the warning than have it. Message reads implicit conversion loses integer precision. Im only working with ints and characters so I don't see what the problem would be.

[Ganado]

std::string::length() returns a number of the type std::string::size_type. This is an unsigned type that is guaranteed to be large enough to represent the size of any string. You could also just use "size_t" instead, which is also guaranteed to be large enough.

size_t len = frequent.length();

[Mount eerie]

Interesting I didn't know that. What is size_t ive never used that before

[Ganado]

http://en.cppreference.com/w/cpp/types/size_t

Here's some notes on the explanation and use of size_t:

std::size_t can store the maximum size of a theoretically possible object of any type (including array).

std::size_t is commonly used for array indexing and loop counting. Programs that use other types, such as unsigned int, for array indexing may fail on, e.g. 64-bit systems when the index exceeds UINT_MAX or if it relies on 32-bit modular arithmetic.

When indexing C++ containers, such as std::string, std::vector, etc, the appropriate type is the member typedef size_type provided by such containers. It is usually defined as a synonym for std::size_t.

It's usually a typedef for unsigned long long.

[jonnin]

for that matter my int counts probably should be unsigned 64 bit for pure code. Your string has a length of 10 --- a signed char is just as good here, in practice.

[Ganado]

Yeah, in practice it's fine, it's just using the signed int = unsigned assignment is what generates the compiler warning.

[lastchance]

In the spirit of keeping it simple ... to find the maximum frequency only:

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

//======================================================================

int maxFrequency( const string &str )
{
   int f[10] = { 0 };
   for ( char c : str ) if ( isdigit( c ) ) f[ c - '0' ]++;
   return *max_element( f, f + 10 );
}

//======================================================================

int main()
{
   vector<string> TESTS = { "gh9k8k8k8", "123abc321789", "abc00112", "abc" };
   for ( string s : TESTS ) cout << s << ":  " << maxFrequency( s ) << endl;
}

//====================================================================== 

gh9k8k8k8:  3
123abc321789:  2
abc00112:  2
abc:  0

If you want the modal digits as well you have to work a little harder:

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

//======================================================================

int maxFrequency( const string &str, vector<int> &mode  )
{
   mode.clear();
   int f[10] = { 0 };                                                        // To hold frequency of each digit

   for ( char c : str ) if ( isdigit( c ) ) f[ c - '0' ]++;                  // Tally frequencies

   int maxf = *max_element( f, f + 10 );                                     // Find largest frequency
   if ( maxf == 0 ) return 0;                                                // No digits -> no modes
   
   for ( int i = 0; i < 10; i++ ) if ( f[i] == maxf ) mode.push_back( i );   // Set modes

   return maxf;
}

//======================================================================

int main()
{
   vector<int> mode;
   vector<string> TESTS = { "gh9k8k8k8", "123abc321789", "abc00112", "abc" };

   for ( string s : TESTS )
   {
      int most = maxFrequency( s, mode );
      cout << "String:         " << s    << '\n';
      cout << "Max frequency:  " << most << '\n';
      cout << "Modal digit(s): ";   for ( int i : mode ) cout << i << " ";
      cout << "\n\n";
   }
}

//====================================================================== 

String:         gh9k8k8k8
Max frequency:  3
Modal digit(s): 8 

String:         123abc321789
Max frequency:  2
Modal digit(s): 1 2 3 

String:         abc00112
Max frequency:  2
Modal digit(s): 0 1 

String:         abc
Max frequency:  0
Modal digit(s):