Best of CAT (Common Admission Test) - 2

This post is the second in the series of my efforts to solve some of the best CAT problems in both theory and programming. It gives me a great pleasure to solve and then verify the answers to some puzzles using C++ or Python and sometimes SAS.

Here is an interesting puzzle that will make you look like a geek (or a nerd - depends on how you look at Mathematics) when you pose it to a group.

Question: There is a certain number X which when divided by Y, where all Y ε [1,10] yields a remainder (Y-1). That is, when X is divided by Y, which takes all values from 1 through 10, the remainder is (Y-1). To be more clear, if X is divided by 10 then the remainder is 9, if X is divided by 9 then the remainder is 8, so on and so forth, if X is divided by 3 then the remainder is 2. The condition should hold good for all numbers from 1 to 10. What is the least number X can take to satisfy this condition? (Hint: X is less than 3000.)

Solution: I programmed this in C++ and it is pretty straight-forward.

The same thing can be implemented in SAS. Let me withhold the answer for now.

Coming to the more important part - to solve this problem by implemting theoritical concepts. This problem pertains to Number Theory. 'Least Common Multiple' doesn't need any introduction. When there are a set of divisors that yield the same remainder (Remainder = 1 in this case), the least number that satisfies this condition =

LCM of those divisors - Common remainder.

By solving, the LCM of numbers 1 through 10 is 2520. Hence the answer = 2520 - 1 = 2519.

All multiples of LCM have the same property. (5040 - 1), (7560 - 1) etc, all have the same property. The objective here is to obtain the least number which satisfies the condition which is 2519. More often than not, confusion prevails in CAT. Also, time is premium in these tests and so the standard method of obtaining LCM may not work well if the divisors are too many or too big. Taking cues from the answers and back solving will be lot helpful. In this problem, it is stated that division by 10 yields 9 which implies that the last digit is 9. That holds the key to solve this problem.

Best of CAT (Common Admission Test) - 1

After a relatively refreshing hibernation, I am back to my web log to write a simple terse article, which is the beginning of a series of such articles that deal with some of the best CAT puzzles I encountered. Computational Mathematics - a domain that I am wildly passionate about, is trying to solve these puzzles in both theory and programming. I will start off with a very simple CAT problem that I encountered sometime back. It was rather interesting and deals with Number Theory, which is one of my favorite areas in Mathematics. I transitioned this logic in C++ and it was truly a good exercise.

It is to determine number of zeros in a given number's factorial. Determining the number of zeros in say, 10! is pretty straightforward. But to determine number of zeros in 100! for example is unwieldly - especially from an examination point of view.

Question: What are the number of zeros in 100!

Solution: To determine number of 0's, it is equivalent to determine how many 10's make up the number. For that 10 = 2 x 5 and (2,5) are co-prime. Hence the number of 10's in number N can be determined by N/5 + N/5^2 + N/5^3+ ..... + N/5^n, as long as N/5^n > 1. '^' stands for exponential operator.

=> 100/5 + 100/5^2
=> 20 + 4 = 24.

Answer: 24

I built this into C++ and the code is intuitive.



Click on this code image to enlarge. Also, edit your headers/libs as necessary.

I will keep posting similar problems (especially from CAT) and I believe this would be mutually beneficial.

Idioms in Code (Google Blogoscoped)

It's been a while that I came across such innovative 'verbal' programming. A great compilation...

// idiom 1
cop[0].goodInPercent = 100;
cop[1].goodInPercent = 0;

// idiom 2
isCrowd = personCounter >= 3;

// idiom 3
injury += insult;

// idiom 4
1: board.draw();
goto 1;

// idiom 5
if (bird[1].feather == bird[2].feather) {
 bird[1].flock(bird[2]);
}

// idiom 6
a = getThickness('blood');
b = getThickness('water');
assert(a > b);

// idiom 7
a_spade_a_spade();

// idiom 8
die(1000);
function die(max) {
 for (i = 1; i <= max; i++) {        cut();    } }  // idiom 9 prey = 'worm'; time = getCurrentTime(); if (time >= 4 && time <= 8) {    bird.catch(prey); }  // idiom 10 while ( rome.fire() ) {    doFiddle(); }  // idiom 11 function getValue(garbage) {    return garbage; }  // idiom 12 take(salt * .01);  // idiom 13 var here = false; var there = false;  // idiom 14 if (i == 2) {    tango(); }  // idiom 15 days = 365; for (day = 1; day <= days; day++) {    if ( random(0,100) <= 50 ) apple++; } if (apple <= days) doctor();  // idiom 16 if ( !dogs.sleep() ) {    disturb(dogs); }  // idiom 17 function tunnel() {    var dark;    for (i = 0; i < dark =" true;" dark =" !dark;" a =" 0;" b =" 1;">= 1;
}

// idiom 23
if (cooks >= 3) {
 broth = null;
}

// idiom 24
if (a != 'cake') a.eat();

// idiom 25
doesStand = you == me;

// idiom 26
var location = getLocation();
if (location == 'rome') {
 do( location.getCitizen() );
}

[By Philipp Lenssen | Origin: Idioms in Code (Take a Guess)