1
\$\begingroup\$

How do I find the number of unique digits in a given number.

e.g
if 'input1' is 252 it must return 1, since 5 is the non-repeating digit;
if 'input1' is 25000 it must return 2, since digits 2 and 5 are the only non-repeating ones.

Is there a better way to solve this problem?

// COUNT UNIQUE DIGITS

int nonRepeatDigitsCount(int input1){
int i=0,j,k;
int n=input1;
int count=0,check,c2=0;

// FINDING NUMBER OF DIGITS ON THE GIVEN NUMBER
while(n>0){

    n=n/10;
    c2++;
    }
//CREATING ARRAY OF THE 'c2' SIZE       
int arr[c2];
n=input1;
//STORING INDIVIDUAL DIGITS IN THE ARRAY
while(n>0)
{
    arr[i]=n%10;
    n=n/10;
    i++;

}
// CONDITION TO FIND NON REPEATING DIGITS
for(j=0;j<c2;j++)
{
    check=0;

    for(k=0;k<c2;k++)
    {
          if(j!=k)
          {
           if(arr[j]==arr[k])
           {
            check++;
           }
          } 

    }

    if(check==0)
     {
        count++;
     }
 }

return count;
}
\$\endgroup\$
0
5
\$\begingroup\$

This is needlessly complicated and inefficient. Rather than making an array of all digits in the array, you should make an array of counted occurrences. Since a digit can have a value 0 to 9, this array size will be 10. For each occurrence, increase the value of the index in the array corresponding to the digit by 1.

This also means that you can count non-repeating characters on the fly while iterating through the number. When the number of occurrences is exactly 1, it should be counted. If more than that, it shouldn't.

This makes the code behave the same no matter the number of digits used as input.

Example:

#include <stdio.h>

int non_repeating (int val)
{
  if(val == 0) // special case, value 0 gives 1 digit
  {
    return 1;
  }

  int digit_count[10]={0};
  int non_rep=0;

  for(; val!=0; val/=10)
  {
    int i = val%10;
    digit_count[i]++;

    if(digit_count[i]==1)
    {
      non_rep++;
    }
    else if(digit_count[i]==2)
    {
      non_rep--;
    }
  }

  return non_rep;
}

int main (void)
{
  printf("%d %d\n", 252,        non_repeating(252));
  printf("%d %d\n", 25000,      non_repeating(25000));
  printf("%d %d\n", 1234567890, non_repeating(1234567890));
  printf("%d %d\n", 0,          non_repeating(0));
}

Output:

252 1
25000 2
1234567890 10
0 1
\$\endgroup\$
2
  • \$\begingroup\$ Yeah, this is far better than what I did. Thanks! \$\endgroup\$ – Aditya Mar 25 '19 at 15:09
  • 1
    \$\begingroup\$ Special if(val == 0) case not needed if for() loop replaced with do { } while () loop. \$\endgroup\$ – chux - Reinstate Monica Dec 1 '20 at 17:46
1
\$\begingroup\$

Can the number be negative? If not, then prefer to use an unsigned type as the parameter; if it can, then C99 specifies that the result of division is rounded toward zero: the result of % may be negative.

Apart from that, the simplest and clearest approach is to maintain an array of counts for each digit, as suggested by Lundin. Or even simply an array of booleans, since we're only interested in presence, rather than quantity.

\$\endgroup\$
6
  • \$\begingroup\$ The input lies between 1-25000 lets say. \$\endgroup\$ – Aditya Mar 25 '19 at 15:10
  • \$\begingroup\$ As number sign does not affect the number of unique digits an easy way to cover also the negative num case is to abs() it before performing the actual processing \$\endgroup\$ – Nicola Bernini Apr 24 '19 at 14:27
  • 1
    \$\begingroup\$ @NicolaBernini - take care with abs() - remember that on 2's-complement machines, abs(INT_MIN) is negative... \$\endgroup\$ – Toby Speight Apr 24 '19 at 14:33
  • 1
    \$\begingroup\$ On 2's-complement machines, abs(INT_MIN) is UB. \$\endgroup\$ – chux - Reinstate Monica Dec 1 '20 at 17:42
  • 1
    \$\begingroup\$ Regarding the boolean array: I don't think you can distinguish (0, 1, other) with that. \$\endgroup\$ – Roland Illig Dec 2 '20 at 6:37
-1
\$\begingroup\$

Here is my functional solution with improved space complexity based on bit manipulation

Improvements

  • @Lundin has already identified major issues with the author's solution, my solution provides additional improvements which are related to

  • Space

    • no need to count the actual number of times you observe a certain digit, just discriminate between 3 cases: never observed, observed once and observed more than once

    • the once variable represents in its first 10 bits the digits that have been observed once

    • the more variable represents in its first 10 bits the digits that have been observed more than once

  • Style

    • This solution is Functional with all the related advantages (more readable, more concise, ...)

EDIT: My initial solution was in CPP so now I'm adding the C one: it is basically the same logic, all the CPP-specific stuff is not core

C Solution

#include <stdio.h>

/**
  * @brief It just counts the number of 1s in a given binary representation 
  */
unsigned int count_ones(const unsigned int n, const unsigned int partial)
{
    if(n==0) return partial; 
    return ( (n&1)==0 )?(count_ones(n/2, partial)):(count_ones(n/2, partial+1)); 
}

/**
  * @brief It counts the number of unique digits in a given base-10 number 
  */
unsigned int count( const unsigned int num, const unsigned int once, const unsigned int more )
{
    if(num==0) return (count_ones(once, 0)>0)?(count_ones(once, 0)):1;  
    const unsigned int d = num%10; ///< Just to make the code a bit more readable 

    if((once&(1<<d))==0 && (more&(1<<d))==0) return count(num/10, once|(1<<d), more); ///< New digit observed
    if((once&(1<<d))==(1<<d)) return count(num/10, once&(~(1<<d)), more|(1<<d)); ///< Reobservation of a unique digit
    else return count(num/10, once, more); ///< Reobservation of a non unique digit
}


int main(void) {
    // your code goes here
    printf("252 = %d\n", count(252,0,0));
    printf("25000 = %d\n", count(25000,0,0)); 
    printf("1234567890 = %d\n", count(1234567890, 0, 0)); 
    printf("0 = %d\n", count(0,0,0)); 
    return 0;
}

Output

252 = 1
25000 = 2
1234567890 = 10
0 = 1

CPP Solution

#include <iostream>
using namespace std;

/**
  * @brief It just counts the number of 1s in a given binary representation 
  */
unsigned int count_ones(const unsigned int n, const unsigned int partial=0)
{
    if(n==0) return partial; 
    return ( (n&1)==0 )?(count_ones(n/2, partial)):(count_ones(n/2, partial+1)); 
}

/**
  * @brief It counts the number of unique digits in a given base-10 number 
  */
unsigned int count( const unsigned int num, const unsigned int once=0, const unsigned int more=0 )
{
    if(num==0) return max(count_ones(once, 0), static_cast<unsigned int>(1)); 
    const auto d = num%10; ///< Just to make the code a bit more readable 

    if((once&(1<<d))==0 && (more&(1<<d))==0) return count(num/10, once|(1<<d), more); ///< New digit observed
    if((once&(1<<d))==(1<<d)) return count(num/10, once&(~(1<<d)), more|(1<<d)); ///< Reobservation of a unique digit
    else return count(num/10, once, more); ///< Reobservation of a non unique digit
}

int main() {
    // your code goes here
    cout << count(252) << endl;
    cout << count(25000) << endl; 
    cout << count(1234567890) << endl; 
    cout << count(0) << endl; 
    return 0;
}

Output

1
2
10
1
\$\endgroup\$
4
  • 1
    \$\begingroup\$ While this may be an interesting alternative approach in C++, it's not really a review of the code (which is in C). Commenting on what things you do differently, why you are doing it that way and pointing out the flaws in the original code would make this a better answer. Copy-pasting code does not always provide a good learning experience. \$\endgroup\$ – Edward Apr 24 '19 at 14:11
  • \$\begingroup\$ Hi @Edward, I have edited my solution adding the version in C (it is basically the same logic as all the CPP stuff is not core) and explaining the improvements Hope it is better now \$\endgroup\$ – Nicola Bernini Apr 24 '19 at 14:24
  • \$\begingroup\$ Using recursion in C is not necessarily good style. Counting the number of 1-bits recursively is also slow since the CPU spends most of the time managing memory. If there's no __builtin_popc available, the canonical code for the popc operation comes from the book Hacker's Delight. \$\endgroup\$ – Roland Illig Apr 24 '19 at 19:41
  • \$\begingroup\$ Your code is far from being easy to read. Counting the number of non-repeating digits is a typical task for a beginner programmer, and your code is much too complicated for a beginner. All these << operators, the missing spaces and the long lines of code make the code hard to read even for advanced programmers. \$\endgroup\$ – Roland Illig Dec 2 '20 at 6:47
-2
\$\begingroup\$

if input=n then the java code is,

int a[]=new int[10];
int rem;
int count=0;

while(n>0)
{
rem=n%10;
a[rem]=++a[rem]
n=n/10;
}
 for(int i=0;i<10;i++)
{
if(a[i]==1)
 count++;
}
return count;   // is the output
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Welcome to Code Review! You have presented an alternative solution, but haven't reviewed the code. Please explain your reasoning (how your solution works and why it is better than the original) so that the author and other readers can learn from your thought process. \$\endgroup\$ – Toby Speight Dec 1 '20 at 17:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.