A way of checking if the digits of num1 are the digits in num2 without checking each digit?

Question

Lets say I have guessed a lottery number of:

1689

And the way the lottery works is, the order of the digits don't matter as long as the digits match up 1:1 with the digits in the actual winning lottery number.

So, the number 1689 would be a winning lottery number with:

1896, 1698, 9816, etc..

As long as each digit in your guess was present in the target number, then you win the lottery.

Is there a mathematical way I can do this?

I've solved this problem with a O(N^2) looping checking each digit against each digit of the winning lottery number (separating them with modulus). Which is fine, it works but I want to know if there are any neat math tricks I can do.

For example, at first... I thought I could be tricky and just take the sum and product of each digit in both numbers and if they matched then you won.

^ Do you think that would work?

However, I quickly disproved this when I found that lottery guess: 222, and 124 have the different digits but the same product and sum.

Anyone know any math tricks I can use to quickly determine if the digits in num1 match the digits in num2 regardless of order?

Answer 1

Split into array, sort array, join into string, compare strings.

(Not a math trick, I know)

Answer 2

I'd sort both number's digits and compare them.

Answer 3

Sort digits before storing a number :-) After that, your numbers will be equal.

Answer 4

You can place the digits into an array, sort the array, then compare the arrays element by element. This will give you O( NlogN ) complexity which is better than O( N^2 ).

Answer 5

If you are only dealing with 4 digits I dont think you have to put much thought into which algorithm you use. They will all perform roughly the same.

Also 222 and 124 dont have the same sum

Answer 6

You have to consider that when n is small, the order of efficiency is irrelevant, and the constants start to matter more. How big can your numbers actually get? Can you get up to 10 digits? 20? 100? If your numbers have just a few digits, n^2 really isn't that bad. If you have strings of thousands of digits, then you might actually need to do something more clever like sorting or bucketing. (i.e. count the 0s, count the 1s, etc.)

Answer 7

How about going through each number, and counting up the number of appearances of each digit (into two different 10 element arrays)? After you'd done the totaling, compare the counts of each digit. Since you only look at each digit once, that's O(N).

Code would look something like:

for(int i=0; i<digit_count; i++)
{
   guessCounts[guessDigits[i] - '0']++;
   actualCounts[actualDigits[i] - '0']++;
}

bool winner = true;
for(int i=0; i<10 && winner; i++)
{
   winner &= guessCounts[i] == actualCounts[i];
}

Above code makes the assumption that guessDigits and actualDigits are both char strings; if they held the actual digits then you can just skip the - '0' business.

There are probably optimizations that would make this take less space or terminate sooner, but it's a pretty straightforward example of an O(N) approach.

By the way, as I mentioned in a comment, the multiplication/sum comparison will definitely not work because of zeros. Consider 0123 and 0222. Product is 0, sum is 6 in both cases.

Answer 8

If N can become large, sorting the digits is the answer.

Because digits are 0..9 you can count the number of occurrences of each digit of the lottery answer in an array [0..9].

To compare you can subtract 1 for each digit you encounter in the guess. When you encounter a digit where the count is already 0, you know the guess is different. When you get through all the digits, the guess is the same (as long as the guess has as many digits as the lottery answer).

Answer 9

For each digit d multiply with the (d+1)-th prime number.

This is more mathematical but less efficient than the sorting or bucket methods. Actually it is the bucket method in disguise.

Answer 10

I'm stealing the answer from Yuliy, and starblue (upvote them)

Bucketing is the fastest aside from the O(1)

lottonumbers == mynumbers;

Sorting is O(nlog2n)

Bucketsort is an O(n) algorithm.

So all you need to do is do it twice (once for your numbers, once for the target-set), and if the numbers of the digits add up, then they match. Any kind of sorting is an added overhead that is unnecessary in this case.

array[10] digits;
while(targetnum > 0)
{
    short currDig = targetnum % 10;
    digits[currDig]++;
    targetnum = targetnum / 10;
}
while(mynum > 0)
{
    short myDig = mynum % 10;
    digits[myDig]--;
    mynum = mynum / 10;
}
for(int i = 0; i < 10; i++)
{
   if(digits[i] == 0)
      continue;
   else
     //FAIL TO MATCH
}

Not the prettiest code, I'll admit.

Answer 11

Create an array of 10 integers subscripted [0 .. 9].

Initialize each element to a different prime number

Set product to 1.

Use each digit from the number, to subscript into the array, pull out the prime number, and multiply the product by it.

That gives you a unique representation which is digit order independent.

Do the same procedure for the other number.

If the unique representations match, then the original numbers match.

Answer 12

If there are no repeating digits allowed (not sure if this is the case though) then use a 10-bit binary number. The most significant bit represents the digit 9 and the LSB represents the digit 0. Work through each number in turn and flip the appropriate bit for each digit that you find

So 1689 would be: 1101000010

and 9816 would also be: 1101000010

then a XOR or a subtract will leave 0 if you are a winner

This is just a simple form of bucketing

Answer 13

Just for fun, and thinking outside of the normal, instead of sorting and other ways, do the deletion-thing. If resultstring is empty, you have a winner!

    Dim ticket As String = "1324"
    Dim WinningNumber As String = "4321"

    For Each s As String In WinningNumber.ToCharArray
        ticket = Replace(ticket, s, "", 1, 1)
    Next

    If ticket = "" Then MsgBox("WINNER!")
    If ticket.Length=1 then msgbox "Close but no cigar!"

This works with repeating numbers too..

Answer 14

One cute solution is to use a variant of Zobrist hashing. (Yes, I know it's overkill, as well as probabilistic, but hey, it's "clever".)

Initialize a ten-element array a[0..9] to random integers. Then, for each number d[], compute the sum of a[d[i]]. If the numbers contained the same digits, the resulting numbers will be equal; with high probability (~ 1 in how many possible ints there are), the opposite is true as well.

(If you know that there will be at most 10 digits total, then you can use the fixed numbers 1, 10, 100, ... instead of random numbers for guaranteed success. This is bucket sorting in not-too-much disguise.)