CODEWITHSUNDEEP
c++find-occurrences
Shubh Tripathi
Shubh Tripathi

Reputation: 100

Check whether occurrence of individual digit in a number is same or not

We need to check whether the occurrence of an individual digit in a number is same or not.For e.g. for 2244 (2 occur 2 times and 4 occur 2 times).Therefore, occurrence of both digits are same.

//This will return true if occurrence of individual digit in
//a number is same else false

bool stable(int no)
{
    vector<int> v1;
    int k , count = 1;
    int arr[10];
    //Initializing all arr[] -> 0
    for(int k = 0 ; k < 10 ;k++)
    {
        arr[k] = 0;
    }
    while(no != 0)
    {
        k=no%10;
        arr[k]++;
        no=no/10;
    }
    for(int i = 0 ; i < 10 ; i++)
    {
        if(arr[i] != 0)
        {
            v1.push_back(arr[i]);  //storing count of individual digits
        }
    }
    vector<int>::iterator it , it2;
    for(it = v1.begin()+1 ,it2 = v1.begin(); it != v1.end() ; it++,it2++)
    {
        if(*it == *it2) //if all the values are same return true else false
        {
            count++;
        }
    }
    if(count == v1.size()) return true;
        return false; 
}

But this code doesn't work for no like 2222,1111,444. Also, would you suggest some good way to optimize the code?

Upvotes: 0

Views: 1790

Answers (3)

WhozCraig
WhozCraig

Reputation: 66214

I think you're making this harder than it needs to be (or I'm severely misunderstanding the question, which happens often).

The assumption is the requirements are as specified: Given a non-zero positive value, a number is qualified if all digits appear with equal frequency, including 1 (ex: 1122, 2222, 1234 all qualify, as no digit has higher frequency than any other).

The algorithm is simple:

  1. Quick return for any value less than 10; a single digit number is immediately qualified.
  2. Build a counter array of modulus residuals.
  3. Find the first non-zero value in the array
  4. From that point on, find the first non-zero value that does NOT match the value from (4). If you reach the end of the sequence without finding such a difference, all digits in the original number must have the same count.

In all the complexity is logarithmic base-10 to the input number plus a single-pass scan of the constant-sized array (10 elements).

Example Code

#include <algorithm>
#include <iterator>

bool stable(unsigned value)
{
    if (value < 10) // single digit only, including zero
        return true;

    unsigned ar[10]={0};
    do { ++ar[value%10]; } 
    while (value /= 10);

    auto it = std::find_if(std::begin(ar), std::end(ar),
                            [](auto n) { return n != 0; });
    return std::find_if(std::next(it), std::end(ar),
                        [it](auto n){ return n && (n != *it);}) == std::end(ar);
}

You could always further this by retaining the maximum digit count and leaving without the find operations if it ultimately was 1 (ex: 1234, 102938 are such examples). I'll leave that as an exercise for you to benchmark to determine if there is any performance benefit. I honestly doubt there will be.

Upvotes: 1

Rajeev Singh
Rajeev Singh

Reputation: 3332

While checking if all the repeated counts are same, you can directly return false if counts do not match, no need to check further. If the vector contains only a single count for numbers like 2222, 1111 it will return true.

vector<int>::iterator it , it2;
for(it = v1.begin()+1 ,it2 = v1.begin(); it != v1.end() ; it++,it2++)
{
    if(*it != *it2) //if two values are not same return false
    {
        return false;
    }
}
return true;

Upvotes: 0

Kostas
Kostas

Reputation: 4176

Try this:

bool stable(int no)
{
    std::vector<int> v1;

    while (no != 0){
        v1.push_back(no%10);
        no /= 10;
    }

    std::sort(v1.begin(), v1.end()); //SORTING DIGITS IN ASCENDING ORDER

    std::vector<int> index = {0};  //BUILDING VEC WITH INDEXES WHERE CHANGES HAPPEN
    for (unsigned int i = 0; i < v1.size()-1; ++i){
        if (v1[i] != v1[i+1])
            index.push_back(i+1);
    }
    //EDGE CASE WHEN ONLY 1 DIGIT APPEARS (e.g. 555)
    if (index.size() == 1)
        return true;

    //CHECKING THAT ALL INDEXES ARE EQUALLY SEPARATED
    int diff = index[1] - index[0];
    for (unsigned int i = 1; i < index.size()-1; ++i){
        if (index[i+1] - index[i] != diff)
            return false;
    }
    return true;
}

Upvotes: 1

Related Questions