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.

Google's Chrome: What's the strategy?

It is disconcerting to even start thinking that Chrome was launched just to take on Microsoft's Internet Explorer or Mozilla's Firefox. I am pretty sure that this is not high on the 'Mission' list of Google, though a direct competition is intentional and inevitable. That leads to the question - What could be the strategy behind this move. Google is always known for its innovative projects and subtle debuts. They have a vast repertoire of such products and you never know what is coming next. This unpredictablity is Google's greatest weapon. Anyways, moving on to Chrome.

Let me start from the basics. Why do we need a computer? In no particular order - we use computers for casual browsing, news, personal (music/media), chat, office work (technical & non-technical stuff). There could be couple of other things that I may have missed out. Most of these, infact all of them, have been traditionally on desktop software. And this is Microsoft's stronghold. There are some conventions that we got used to - like saving our files on our hard-disks, transferring files using optical media, using the computer to access internet. And then came Google, riding the internet wave.  And it had a web-based business model. In other words, Google wants to use the potential of internet as an application platform and move the market away from conventional PC-based environment to a web-based one. And the starting point for this transition is Chrome. 

One may wonder the necessity to come up with a new browser when big guns IE, Firefox and Safari have saturated browser market. Well, for a complete integration of all its web-based applications it is no-brainer that Google will want to come up with an in-house browser than rely on a 'third-party' browser. It will give them better control on scalability of their applications and control over the evolution of various components related to their business. The beta version of Chrome is adequate. Firefox and IE 8 are far superior in features and reliability to Chrome but it is foolish to compare these three at this point. Chrome is in its infancy and is building a base to lauch its horde of services. Google's core business - its search engine is, ofcourse, web-based. The applications they provide like GMail are on the network. Google docs, a direct competitor to MS Office, is web-based. All of these help Google rake in advertising. So, what's the need for desktop software? Read Windows, Office.

It is too early to predict the penetration of Chrome into the browser market. The features are minimal but the potential is maximal. Once Google is ready to integrate its applications to Chrome, imagine this, all one needs to do is boot the computer and open Chrome. You can search from Chrome's navigation bar, open office suite from Chrome, chat through Chrome, watch movies here and what else do you need to do?

And what could be the impact of Chrome on Microsoft? Microsoft is tied to its legacy model of selling licenses of Windows & Office and is now realizing the potential of internet. Microsoft Office has a lion's share in Microsoft's revenue. And if Google can capitalize on its online office suite, it would be a huge blow to Microsoft. But, it'd be naive to write off Microsoft. Who know what they have in store. Are they transitioning to an online-office model? Not easy but not impossible either. For their benefit, I feel Microsoft should stop worrying about 'fancy vista' stuff and concentrate on functionality and user friendly apps/suites. Else they could find themselves swimming upstream very soon.

So, Chrome is here to stay. It cannot be compared to IE or Firefox right now, but I feel it has the ability to better both these browsers and above all, be more useful to the user. There are many 'to-do' items for Chrome of which the most important are stability and security. It's still a beta so chill and wait for the real version to roll-out.

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.