A Programming Puzzle
June 28, 2013
The function has to do two different things on the two calls. It took me two days to figure out that I could encode the desired action by handling odd numbers and even numbers separately. The key insight is to separate the sign and magnitude of the number by the parity of the number. So there are three rules:
1) If the number is even, it keeps the same sign and moves 1 closer to 0; thus, subtract 1 from a positive even number and add 1 to a negative even number.
2) If the number is odd, it changes sign and moves 1 farther from 0; thus, multiply by -1 and subtract 1 from a positive odd number and multiply by -1 and add 1 to a negative even number.
3) As a special case, 0 is unchanged; it has no sign, so it can’t change its sign.
Here’s the function:
(define (f n)
(cond ((and (positive? n) (even? n)) (- n 1))
((and (negative? n) (even? n)) (+ n 1))
((and (positive? n) (odd? n)) (- (- n) 1))
((and (negative? n) (odd? n)) (+ (- n) 1))
And here are some examples:
> (f (f -3))
> (f (f -2))
> (f (f -1))
> (f (f 0))
> (f (f 1))
> (f (f 2))
> (f (f 3))
You can run the program at http://programmingpraxis.codepad.org/OIoOHeXc.
The source where I found this question claims it was asked at a job interview. I find that hard to believe. Either you get the “Aha!” insight or you don’t, or else you’ve heard and solved the puzzle previously. In any case, the interviewer learns nothing about you. Terrible interview question.
Pages: 1 2