SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

Question from a software interview

July 26th, 2004, 4:48 pm

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.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

July 26th, 2004, 5:29 pm

Last edited by alexandreC on July 25th, 2004, 10:00 pm, edited 1 time in total.
 
User avatar
Ouyang
Posts: 100
Joined: January 17th, 2002, 5:42 am

Question from a software interview

July 26th, 2004, 5:31 pm

(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.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

July 26th, 2004, 5:33 pm

sorry Ouyang, but you do have an "1" in your answer!!!Alex
 
User avatar
chiranjiv
Topic Author
Posts: 31
Joined: July 14th, 2002, 3:00 am

Question from a software interview

July 26th, 2004, 6:23 pm

That's correct Ouyang. AlexandreC, the numbers can "count" themselves too...so a 1 counts itself!
 
User avatar
Mircea
Posts: 19
Joined: July 9th, 2004, 6:04 pm

Question from a software interview

July 27th, 2004, 1:05 pm

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.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

July 27th, 2004, 10:06 pm

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.
 
User avatar
kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

July 28th, 2004, 4:15 pm

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
 
User avatar
Arroway
Posts: 580
Joined: January 19th, 2003, 10:06 pm

Question from a software interview

July 28th, 2004, 8:22 pm

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.
 
User avatar
Wilbur
Posts: 87
Joined: August 12th, 2004, 7:39 pm

Question from a software interview

August 13th, 2004, 12:23 pm

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
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

August 13th, 2004, 2:48 pm

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.
 
User avatar
kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 16th, 2004, 6:26 pm

fwiw:1210, 202021200--3211000 / 42101000 / 521001000 / 6210001000 / 72100001000etc.
 
User avatar
alexandreC
Posts: 678
Joined: June 9th, 2004, 11:35 pm

Question from a software interview

August 16th, 2004, 10:24 pm

nice one kr.are there other numbers that, not belonging to your pattern, satisfy the requirment?Alex
 
User avatar
kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 17th, 2004, 1:30 pm

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!
 
User avatar
kr
Posts: 1885
Joined: September 27th, 2002, 1:19 pm

Question from a software interview

August 17th, 2004, 3:00 pm

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

PW by JB

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...


Twitter LinkedIn Instagram

JOBS BOARD

JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...


GZIP: On