Computer Science Canada

a counting problem
Author:  Nischal Regmi [ Tue May 25, 2010 4:59 am ]
Post subject:  a counting problem
I have faced a counting problem. How many 4-digit numbers are there having three same digits? I think it is 360, but i'm not sure. Can any one explain the correct answer?
Author:  andrew. [ Tue May 25, 2010 2:42 pm ]
Post subject:  RE:a counting problem
What exactly do you mean? Do you mean like this:
0000
0001
0002
...
1110
1112
...
2111
...
2202

Are all of those numbers valid in your question?
Author:  jcollins1991 [ Tue May 25, 2010 3:06 pm ]
Post subject:  Re: a counting problem
If leading zero's are counted it'd be 410 ways or something, so he's probably looking for numbers starting at 1000 and ending at 9999
Author:  chrisbrown [ Tue May 25, 2010 3:21 pm ]
Post subject:  Re: a counting problem
Nischal Regmi @ Tue May 25, 2010 4:59 am wrote:
I have faced a counting problem. How many 4-digit numbers are there having three same digits? I think it is 360, but i'm not sure. Can any one explain the correct answer?

You are correct based on the following assumptions:
(a) 4-digit numbers can start with 1 or more zeros, i.e. 0001, 0111 are both valid.
(b) You exclude numbers with four identical digits, i.e. 0000, 1111 are invalid.

I can't explain how to find the answer mathematically, but this Quick n' Dirty? Java program will compute it:
Java:
public class CountDigits {

        private static String padWithZeros(String num) {
                if ( num.length() < 4 ) return padWithZeros("0" + num); // Delete this line to account for case (a)
                return num;          
        }
       
        private static boolean has3(String num) {
                int[] count = new int[10];
                do count[Integer.parseInt(num.substring(0, 1))]++;
                while ( ! "".equals(num = num.substring(1)) );
                for (int i = 0; i < 10; i++) if (count[i] == 3) return true; // Change to count[i] >= 3 to account for case (b)
                return false;
        }
       
        public static void main(String[] args) {
                int c = 0;
                for (int i = 0; i < 10000; i++) if ( has3(padWithZeros(new Integer(i).toString()))) c++;
                System.out.println("Numbers with a digit repeated exactly 3 times: " + c);

        }
}
Author:  andrew. [ Tue May 25, 2010 3:49 pm ]
Post subject:  RE:a counting problem
Is 1101 valid?
Author:  Unnamed.t [ Tue May 25, 2010 4:36 pm ]
Post subject:  Re: a counting problem
The following code should be quite precise. I'm sorry its so messy and yes I know it can be greatly shortened (for example, running all calculations in one for loop), but this is just a draft to see if it actually fits to answering the problem.

I have counted numbers from 1000 to 9999 in one for loop and numbers 0000 to 0999 in a separated for loop. I have excluded the evaluation of numbers with 4 of the same digits (e.g. 1111). In the end there were 370 4 digit numbers that have 3 of the same digits (including numbers that start with 0 (e.g. 0001, 0002, 0100)). There are 333 numbers from the range 1000 to 9999 and 37 numbers from 0 to 999.

You can also view all the numbers that were counted by taking out the commented lines that output vars count and count2.

Java:

public class DigitCount
{
    public static void main (String[] args)
    {
        int j = 0;
        int l = 0;
        char a, b, c, d;
        for (int i = 1000 ; i < 10000 ; i++)
        {
            String count = Integer.toString (i);
            a = count.charAt (0);
            b = count.charAt (1);
            c = count.charAt (2);
            d = count.charAt (3);

            if (a == b && b == c && a == c || a == c && a == d && c == d || a == b && a == d && b == d || b == c && b == d && c == d)
            {
                //System.out.println (count);
                j++;
            }
        }

        System.out.println (j);

        for (int k = 0 ; k < 1000 ; k++)
        {
            String count2 = Integer.toString (k);

            if (k < 10)
                count2 = "000" + count2;

            else if (k > 9 && k < 100)
                count2 = "00" + count2;

            else
                count2 = "0" + count2;
            a = count2.charAt (0);
            b = count2.charAt (1);
            c = count2.charAt (2);
            d = count2.charAt (3);

            if (a == b && b == c && a == c || a == c && a == d && c == d || a == b && a == d && b == d || b == c && b == d && c == d)
            {
                //System.out.println (count2);
                l++;
            }
        }
        System.out.println (l);
        System.out.println (l + j);
    }
}
Author:  jcollins1991 [ Tue May 25, 2010 5:15 pm ]
Post subject:  Re: a counting problem
OOOOOOPSSSSSS... I thought I was under counting when I was actually over counting... Here's the right way:

You have 4 spots, 3 are going to be taken
_XXX, X_XX, XX_X, XXX_

So you have 4 ways you can place the 3 digits together

There are 10 options for the 3 digits together, so now you have 40 ways to place the 3 digits. Now to fill in the empty spot you don't want the same digit, so you only have 9 options after you've chosen the triplet digit. So 9 * 40 = 360 possible ways...
Author:  Unnamed.t [ Tue May 25, 2010 5:53 pm ]
Post subject:  Re: a counting problem
Quote:
You have 4 spots, 3 are going to be taken
_XXX, X_XX, XX_X, XXX_

So you have 4 ways you can place the 3 digits together

There are 10 options for the 3 digits together, so now you have 40 ways to place the 3 digits. Now to fill in the empty spot you don't want the same digit, so you only have 9 options after you've chosen the triplet digit. So 9 * 40 = 360 possible ways...


Wow what you said actually makes a lot of sense. But, there has to be some kind of mistake in that logic that oversees 10 possibilities. It is really hard to say, but my program says there are 370 in it doesn't seem to repeat any numbers or overdo any of the counting.

Hopefully there will be more algorithms uploaded to support the 360 or 370 number possibilities.
Author:  jcollins1991 [ Tue May 25, 2010 6:04 pm ]
Post subject:  Re: a counting problem
It's 360, the extra 10 are when they're all the same making it 370 total... The question isn't completely clear as to only 3 of the same digit or atleast 3 of the same digit, so either answer is right...
Author:  chrisbrown [ Tue May 25, 2010 9:03 pm ]
Post subject:  Re: a counting problem
jcollins1991 @ Tue May 25, 2010 6:04 pm wrote:
The question isn't completely clear [...] so either answer is right...

Interesting logic. Personally, I would seek clarification rather than exploit ambiguities.
Author:  jcollins1991 [ Tue May 25, 2010 9:34 pm ]
Post subject:  Re: a counting problem
chrisbrown @ Tue May 25, 2010 9:03 pm wrote:
jcollins1991 @ Tue May 25, 2010 6:04 pm wrote:
The question isn't completely clear [...] so either answer is right...

Interesting logic. Personally, I would seek clarification rather than exploit ambiguities.


*sigh*... OP said they though the answer was 360 at the very start, I came up with a explanation that gave the same result... 370 is what Unnamed.t said it should be based on their program which also counted when all 4 are the same, I only gave the explanation to why he was getting that...

note: 360 could also be if you're not counting leading zeros but you're counting ones with 4 digits the same
Author:  chrisbrown [ Tue May 25, 2010 9:54 pm ]
Post subject:  Re: a counting problem
jcollins1991 @ Tue May 25, 2010 9:34 pm wrote:
chrisbrown @ Tue May 25, 2010 9:03 pm wrote:
jcollins1991 @ Tue May 25, 2010 6:04 pm wrote:
The question isn't completely clear [...] so either answer is right...
Interesting logic. Personally, I would seek clarification rather than exploit ambiguities.
*sigh*... OP said they though the answer was 360 at the very start, I came up with a explanation that gave the same result... 370 is what Unnamed.t said it should be based on their program which also counted when all 4 are the same, I only gave the explanation to why he was getting that...

That was rude of me, I apologize.


jcollins1991 @ Tue May 25, 2010 9:34 pm wrote:
note: 360 could also be if you're not counting leading zeros but you're counting ones with 4 digits the same

I think that's 342 iirc, both of the cases in my first post.
Author:  jcollins1991 [ Tue May 25, 2010 10:06 pm ]
Post subject:  Re: a counting problem
Oh ya it is 342 >.<... Reason: original 360 - 9 cases where 000_ - 9 cases where XXX0... So many different answers in this thread now the OP just has to choose which one matches his situation XD
Author:  Nischal Regmi [ Tue May 25, 2010 11:30 pm ]
Post subject:  Re: a counting problem
let me state this problem precisely. We have 4-digit numbers, i.e. , from 0 to 9999. we write numbers having less than 4 digits by pre-pending zeros, for example 0 is written as 0000, 32 as 0032 and so on. The problem is to count the following types of numbers
(a) numbers having all four digits different, e.g., 4762, 9348, etc.
(b) numbers having one pair and two different digits, e.g. 3367, 3637, 6337, etc.
(c) numbers having two different pairs, e.g. 7744, 7474, 3443, etc. However, We do not
treat 6666, for example, as two pairs.
(d)numbers having three digits same and one different, e.g. 3337, 3733, 7333, etc.
(e)numbers having all digits same, e.g. 6666, 7777

It is obvious that there are 1000 4-digit numbers in total. Can anybody help be to solve this mathematically?
Author:  jcollins1991 [ Wed May 26, 2010 7:34 am ]
Post subject:  Re: a counting problem
There are 10,000 numbers, not 1,000... Try reading stuff in these links about counting http://www.intmath.com/Counting-probability/Counting-probability-intro.php and http://www.ltcconline.net/greenl/courses/102/Probability/Probability.htm ... If you want to post your own solutions I'd gladly read over them, but me just posting solutions to all of them won't help you learn anything...
Author:  jbking [ Wed May 26, 2010 10:30 am ]
Post subject:  Re: a counting problem
Nischal Regmi @ Tue May 25, 2010 9:30 pm wrote:
let me state this problem precisely. We have 4-digit numbers, i.e. , from 0 to 9999. we write numbers having less than 4 digits by pre-pending zeros, for example 0 is written as 0000, 32 as 0032 and so on. The problem is to count the following types of numbers
(a) numbers having all four digits different, e.g., 4762, 9348, etc.
(b) numbers having one pair and two different digits, e.g. 3367, 3637, 6337, etc.
(c) numbers having two different pairs, e.g. 7744, 7474, 3443, etc. However, We do not
treat 6666, for example, as two pairs.
(d)numbers having three digits same and one different, e.g. 3337, 3733, 7333, etc.
(e)numbers having all digits same, e.g. 6666, 7777

It is obvious that there are 1000 4-digit numbers in total. Can anybody help be to solve this mathematically?


Note: I'll leave a lot of answers in a form of nPr where the solution is n!/r! that should be a straightforward computation or nCr where solution is n choose r or n!/((n-r)!r!)

Well, some of this is a lot like high school Math to my mind. The first case is the easiest since it is simply 10P6 for the total value as you are reducing what possible choices remain each time.

The second set is likely the trickiest as there are some cases where one may well double count things but I'd think it shouldn't be that hard to consider 3-digit numbers where each digit is different. Now, what is left to do is double a digit and count all the possibilities of it and remove any duplicates. If one wants the heavy lifting to enumerate this case, consider some generating functions to possibly add everything up.

The third set while different isn't that hard either as there are 10C2 ways to choose the 2 numbers and then 4C2 ways to arrange them. This does not count all the same as you are assuming 2 different digits similar to above scenarios where the digits are distinct. Multiplying together the possibilities should give the total for this case I'd imagine.

The fourth set has been discussed to death I think so I'll leave that alone.

The fifth set is the simplest as there are 10 numbers as each of 0-9 represents a possibility here.

If after all 5 cases the total isn't 10,000 then there has been something overlooked.
Author:  Unnamed.t [ Wed May 26, 2010 4:54 pm ]
Post subject:  Re: a counting problem
Write your explanation gives us a more vivid sense in what we are looking for. In just mathematical terms (excluding programming) jcollins has given us
a perfect mathematical model.

x = the number of ways to place the three digits together = 4
y = the options for the digits = 10
z = the options for the remaining digit = 9

x*y*z=4*10*9=360

Other models can easily be made for all the counting problems that you have offered us.

Credit for the model:
jcollins1991 wrote:

So you have 4 ways you can place the 3 digits together

There are 10 options for the 3 digits together, so now you have 40 ways to place the 3 digits. Now to fill in the empty spot you don't want the same digit, so you only have 9 options after you've chosen the triplet digit. So 9 * 40 = 360 possible ways...

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy