a counting problem

[Nischal Regmi]

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?

[andrew.]

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?

[jcollins1991]

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

[chrisbrown]

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);         } }

[andrew.]

Is 1101 valid?

[Unnamed.t]

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);     } }

[jcollins1991]

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...

[Unnamed.t]

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.

[jcollins1991]

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...

[chrisbrown]

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.

[jcollins1991]

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

[chrisbrown]

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.

[jcollins1991]

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

[Nischal Regmi]

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?

[jcollins1991]

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...