Check if two numbers have same digits-CodePudding

I need to write a program which will check if two numbers have same digits. For example:

a = 4423, b = 2433;

Even though their digits don't appear the same amount if times, they have same digits.

#include <stdio.h>
#include <stdlib.h>
int same_digit(int a, int b) {
  int n = abs(a), i;
  int count[10];
  for (i = 0; i < 10;   i) {
    count[i] = 0;
  }
  while (n > 0) {
    count[n % 10]  ;
    n = n / 10;
  }
  n = abs(b);
  while (n > 0) {
    count[n % 10]--;
    n = n / 10;
  }
  for (i = 0; i < 10;   i)
    if (count[i] != 0)
      return 0;
  return 1;
}
int main() {
  int a, b;
  scanf("%d", &a);
  scanf("%d", &b);
  if (same_digit(a, b)) printf("Yes");
  else printf("No");
  return 0;
}

Problem with my code is that this literally checks if they have same digits. How could I modify this code to return 1 if all digits from a are present in b, and all digits from b are present in a, no matter how many times they are present.

CodePudding user response：

Your code is a bit more complicated than it needs to be.

Just compute a "has a digit" vector for each number (e.g. each element is 1 if the corresponding digit is in the number). This is a histogram/frequency table except that instead of the count of the digits in a number, it's just 0 or 1.

Then, compare the vectors for equality.

Here's some refactored code:

#include <stdio.h>
#include <stdlib.h>

void
count(int x,int *hasdig)
{
    int dig;

    // handle negative numbers
    if (x < 0)
        x = -x;

    // special case for zero
    // NOTE: may not be necessary
#if 1
    if (x == 0)
        hasdig[0] = 1;
#endif

    for (;  x != 0;  x /= 10) {
        dig = x % 10;
        hasdig[dig] = 1;
    }
}

int
same_digit(int a, int b)
{
    int dig_a[10] = { 0 };
    int dig_b[10] = { 0 };
    int dig;
    int same = 1;

    count(a,dig_a);
    count(b,dig_b);

    for (dig = 0;  dig < 10;    dig) {
        same = (dig_a[dig] == dig_b[dig]);
        if (! same)
            break;
    }

    return same;
}

int
main()
{
    int a, b;

    scanf("%d", &a);
    scanf("%d", &b);

    if (same_digit(a, b))
        printf("Yes\n");
    else
        printf("No\n");

    return 0;
}

CodePudding user response：

You need to store which digits have occurred in both numbers. For example, for both numbers, you could define an array of 10 bool elements, where the first element specifies whether the digit 0 occurred, the second element whether the digit 1 occurred, etc. Since you need two such arrays, you could make an array of 2 of these arrays, giving you a 2D array. That way, you can process both arrays in the same loop.

After you have filled both arrays, you can compare them, in order to determine whether both numbers use the same digits.

Also, it may be better to change the return type of same_digit to bool.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool same_digit( int a, int b )
{
    int numbers[2] = { a, b };
    bool occurred[2][10] = { {false} };

    //determine which digits are used by the individual numbers
    //and fill the two arrays accordingly
    for ( int i = 0; i < 2; i   )
    {
        int n = abs( numbers[i] );

        while ( n > 0 )
        {
            occurred[i][n] = true;
            n = n / 10;
        }
    }

    //determine whether both numbers use the same digits
    for ( int i = 0; i < 10; i   )
        if ( occurred[0][i] != occurred[1][i] )
            return false;

    return true;
}

//the following code has not been modified
int main() {
  int a, b;
  scanf("%d", &a);
  scanf("%d", &b);
  if (same_digit(a, b)) printf("Yes");
  else printf("No");
  return 0;
}

CodePudding user response：

Using arrays is not necessary, but it sure becomes clean code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int cmp(const void *a, const void *b)
{
    return *(char*)a - *(char*)b;
}

int same_digit(int a, int b)
{
    char A[22], B[22]; // Enough for 64 bit. Increase if needed.
    
    sprintf(A, "%d", a);
    sprintf(B, "%d", b);
    
    qsort(A, strlen(A), sizeof *A, cmp);
    qsort(B, strlen(B), sizeof *B, cmp);
    
    return !strcmp(A, B);
}

Demo

Many C coders will frown on this. And it's not completely without good reason. This is how you typically would solve things in Python or Javascript. If you're writing serious C code, there's probably a reason to why you're not choosing a more high level language. And it's quite likely that those reasons has to do with the performance C can offer.

However, there's absolutely nothing that prevents you from starting with this and optimize it later when you have concluded that this code indeed is a bottleneck with a profiler. And who knows? It may be the case that this is faster. Don't do premature optimization.

There are actually many problems involving digits that becomes so much easier if you convert the numbers to arrays of digits first. And many problems involving arrays becomes much easier if you sort the arrays. Don't be afraid to have this approach as a standard tool in your toolbox.

Furthermore, it's quite common that a naive solution for unsorted arrays is O(n²) while a naive solution for a sorted array is just O(n). And since sorting can be done in O(n * log n) or better, you often get a pretty good solution. If I'm not mistaken, this is the case for Wenzels solution. Sure, since n in this case typically is less than 10, it's probably faster anyway. But it's worth remembering. I believe that you would have to write pretty fancy code to solve this in O(n * log n) without arrays. If it's at all possible. (Not saying that it's likely not possible. Only that I don't know)