SERVING THE QUANTITATIVE FINANCE COMMUNITY

• 1
• 2

chiranjiv
Topic Author
Posts: 31
Joined: July 14th, 2002, 3:00 am

### Question from a software interview

Hi All, Dunno if this has been posted eaarlier..but here goes...let a 5-digit number be represented as a b c d e wherea -> number of zeroes in the numberb -> number of 1's in the numberc -> number of 2's in the numberd -> number of 3's in the numbere -> number of 4's in the numberWhat is the number? And how to get it mathematically?
Last edited by chiranjiv on July 25th, 2004, 10:00 pm, edited 1 time in total.

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### Question from a software interview

Last edited by alexandreC on July 25th, 2004, 10:00 pm, edited 1 time in total.

Ouyang
Posts: 100
Joined: January 17th, 2002, 5:42 am

### Question from a software interview

(wrong answer deleted.)Let me try it later.... How about 21200 First a,b,c,d,e is less than 5. We can't have 5 0's. If we have 5 1's, we need 1 ( for 5) + 5 ( for 1's ) digits. The same goes for 2's, 3's, and 4's.Therefore a+b+c+d+e=5 since the sum is the total number of 0's, 1's, 2's, 3's and 4's which is 5 in our case.e can't be greater than 1. If e is 2 then the sum of a,b,c,d, and e will be greater than 5. It can't be 1 either, so e equals 0....
Last edited by Ouyang on July 25th, 2004, 10:00 pm, edited 1 time in total.

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### Question from a software interview

chiranjiv
Topic Author
Posts: 31
Joined: July 14th, 2002, 3:00 am

### Question from a software interview

That's correct Ouyang. AlexandreC, the numbers can "count" themselves too...so a 1 counts itself!

Mircea
Posts: 19
Joined: July 9th, 2004, 6:04 pm

### Question from a software interview

I agree with Ouyang. The only number is 21200. However I use a different line of reasoning. Since a+b+c+d+e=5, e can be only 1 or 0. 1 cannot be since one of the a, b, c, or d must by 4 and the rest 0 (that is 3 zeros)So e = 0Same, d can be only 1 or 0 1 cannot be since we have at least one 1’s and at least one 0’s and one of the a , b, or c equal to 3.So d = 0Then a, b, and c are either 0, 1, or 2. But a = 2 (since e=d=0). Then b+c=3. The only payer that sums to 3 is {1,2}. Then the only possible number is 21200.

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### Question from a software interview

QuoteOriginally posted by: chiranjivThat's correct Ouyang. AlexandreC, the numbers can "count" themselves too...so a 1 counts itself!!!!!I was refering to a previous wrong answer,by Ouyang, that was deleted (and corrected) in the meantime!!....of course that Ouyang's new solution is a good one! Alex
Last edited by alexandreC on July 27th, 2004, 10:00 pm, edited 1 time in total.

kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

### Question from a software interview

1) a <> 02) Let R = # of non-zero digits represented. I.e. if the number is 12320, R = 3. Then R = 4 - {# of b,c,d,e which are zero}, by definition of b,c,d,e. But since a<>0, R = 4 - {# of zeroes in the number} = 4 - a.3) a+b+c+d+e = 5, b/c there are 5 digits in the number.4) Now we rule out the possible R's. - If a=4, R=0, the number is 40000, contradiction, hence a<>4. - a=3 => R = 4 - 3 = 1, and the number must be of the form aa000, a0a00, a00a0, a000a (b/c R=1). But then a+b+c+d+e=2a=5 which is impossible since 2 does not divide 4. - a = 1 => R = 4 - 1 = 3. At the very least, a+b+c+d+e >= 0+0+1+2+3 (3 nonzero representations), but that's 6 > 5, contradiction. Thus a=2.5) Hence the number has the form aba00 or some permutation of digits. b=1 since the digitsum = 5. Thus the only possibility is 21200.QED

Arroway
Posts: 580
Joined: January 19th, 2003, 10:06 pm

### Question from a software interview

QuoteOriginally posted by: MirceaSince a+b+c+d+e=5, EDIT: Never mind, now I understand. But why does it still take me 10 minutes to post? Anyone else have this problem?
Last edited by Arroway on July 27th, 2004, 10:00 pm, edited 1 time in total.

Wilbur
Posts: 87
Joined: August 12th, 2004, 7:39 pm

### Question from a software interview

Why is the number 41000, representing 10000 not acceptable?a=4=# of Zerob=1=# of onesc=0= #of 2sd=0=# of 3se=0=# of 4sWilbur

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### Question from a software interview

QuoteOriginally posted by: WilburWhy is the number 41000, representing 10000 not acceptable?a=4=# of Zerob=1=# of onesc=0= #of 2sd=0=# of 3se=0=# of 4sWilburbecause it contains 3 zeros only... (the number has to "represent" itself...)
Last edited by alexandreC on August 12th, 2004, 10:00 pm, edited 1 time in total.

kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

### Question from a software interview

fwiw:1210, 202021200--3211000 / 42101000 / 521001000 / 6210001000 / 72100001000etc.

alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

### Question from a software interview

nice one kr.are there other numbers that, not belonging to your pattern, satisfy the requirment?Alex

kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

### Question from a software interview

what I realized was that the solution is a fixed point, so if you start with any sequence a_0a_1a_2..a_k, and putf(A) = (#0s in A)(#1s in A)...(#ks in A)then a solution to the problem has to be a fixed point of f. There is a problem in that all the numbers could be the same, in which you'd have k+1 zeroes, i.e. f goes out of range. Notice that f(A) = f(sigma o A), where sigma permutes the elements. So it would be better to act on the set of A's modulo this group action, and then know that some fixed points on the new space are only weak solutions (i.e. if you lift to the un-quotiented space, then f still permutes)). Anyhow, the quotient space is much smaller and I should write a program to show the percolation down to the fixed points... would be a good homework exercise.I didn't want to get into the issue of base-ten representations when k gets large enough, that's not too interesting. But in a finite space, we can do a complete analysis, either we reach (a) an invalid state like f(000000000) (b) a fixed point like 21200=f(21200) or (c) a cycle of length > 1 (and there are many of these, which I'd prefer to ignore)Anyhow, it shows that rather than thinking about the problem, somebody should have said: OK, it's 11:34am, so I'll start with 11340...11340 -> 12011 -> 13100 -> 22010 -> 21200 -> 21200 -> EUREKA!

kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

### Question from a software interview

to add a little color, the quotient space is just the space of partitions of n, where the mapping just zero-pads the partitionso for example, k+1 = 4, partitions are 1111 0112 0022 0013 0004 (as before, sum of a_i's = 4 as well, might as well restrict right away and notice that this space is preserved under f).1111 -> 0004 -> 0013 -> 0112 -> 01120022 -> 0022Of those, 0112 really represents 1210 and is a true fixed point, 0022 represents 2020 and is also a true fixed point, that's everything in this case.