Tuesday, September 20, 2011

Sum of the Digits

A simple puzzle to share with today...

Write a program to find sum of all integers of a given number such that sum is always a single digit.
For instance if the given number is 6789, then answer should be 6+7+8+9 = 30 and then 3+0 =3.

A straight forward logic is to write a recursive function which calculates sum of digits until the it is less than 10. But there an efficient logic than this. Here is that

1. Calculate mod(input_integer,9)
2. if the result is 0 then
       sum of digits reduced to single digit is 9
   else
      value returned in step 1 is the sum of digits of input integer reduced to 9.

Here is my oracle SQL solution,

SELECT DECODE(MOD(INPUT_INTEGER,9),0,9,MOD(INPUT_INTEGER,9))
   FROM DUAL;       

Wednesday, September 14, 2011

Is 100!/(50! x 2^50) an integer?


I just read this puzzle somewhere and realized that this is similar to my earlier post How many zeros does 1000! end with?

Here is the solution to this puzzle,

There is no doubt that 100!/50! is an integer. Hence we just need to find whether 100 x 99 x 98 x ... x 51 will be divisible by 2^50 or not. The mathematical theorem discussed in my earlier post helps us to solve this puzzle as well
let us find the exponents of 2 in 100!
   [100/2] + [100/2^2 ] + [100/2^3 ] + [100/2^4 ] + [100/2^5 ] + [100/2^6 ]
      = 50 + 25 + 12 + 6 +3+1 = 97
Therefore 100! is multiples of 2^97
let us find the exponents of 2 in 50!
    [50/2] + [50/2^2 ] + [50/2^3 ] + [50/2^4 ] + [50/2^5 ]
       = 25 + 12 + 6 +3+1 = 47
Therefore 50! is multiples of 2^47

From the above it is evident that 100! / 50! is multiples of 2^50. Hence 100!/(50! x 2^50) is an integer

Monday, August 29, 2011

Project Euler: What is the sum of both diagonals in a 1001 by 1001 spiral?

Problem#28: What is the sum of both diagonals in a 1001 by 1001 spiral?

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

21 22 23 24 25
20  7  8  9 10
19  6  1  2 11
18  5  4  3 12
17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101. What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

Solution:

Number present in the diagonals of first spiral is 1
Numbers present in the diagonals of second spiral is 3,5,7 and 9
Numbers present in the diagonals of third spiral is 13,17,21 and 25
Numbers present in the diagonals of Fourth spiral is 31,37,43 and 49

From above observation it is easy to conculde the following,

1. Every spiral has 4 diagonal numbers (except the first 1)
2. Diagonal numbers same spirals are arithmetic sequences
         3,5,7 and 9 with 2 as common difference
         13,17,21 and 25 as 4 as common difference
3. The value common difference in spiral s is 2(s-1)
     Ex: common diff of spiral 3 is 6 and spiral 4 is 8
4. The difference between last number of spiral s-1 and first number of spiral s is also  2(s-1).
     Ex: diff between last number and first number of spiral 2 and 3 respectively is 4 ( 13 -9)
         diff between last number and first number of spiral 3 and 4 respectively is 6 ( 31 -25)
5. Number of spirals in NxN matrix is N/2 + 1/2.       

The following PL/SQL solution is written based on the above findings,

DECLARE
   lv_final_value   NUMBER (10);
   lv_iter_value    NUMBER;
   lv_factor      NUMBER;
BEGIN
   lv_final_value := 1;
   lv_iter_value := 1;

   FOR i IN 2 .. 501
   LOOP
      lv_factor := 2 * (i - 1);
      lv_final_value := lv_final_value +lv_iter_value * 4 + lv_factor * 10;
      lv_iter_value := lv_iter_value + lv_factor * 4;
   END LOOP;

   DBMS_OUTPUT.PUT_LINE (lv_final_value);
END;



Answer: 669171001

Tuesday, August 2, 2011

How many zeros does 1000! end with?

Is it easy to find the number of zeros 1000! ends with? The answer is YES, it is very straight forward and the answer is 249.
[For the people who does not understand n!(n Factorial).
     1000! is called '1000 factorial' which is equivalent to 1 x 2 x 3 ...x1000.

The answer is [1000/5] + [1000/5^2 ] + [1000/5^3 ] + [1000/5^4 ]...  
             = [1000/5] + [1000/25] +[1000/125] + [1000/625]
             = 200 + 40 + 8 +1 = 249
( [n/p] stands for integer part of n/p. For instance [3/2 ] is 1 and [5/6] is 0. in computer terms FLOOR)

Rest of this post is only for the people who wants to know little more about the mathematical theorem stands behind this solution

Theorem:
if N is an integer, P is a prime number and N! = p^s . m then s = [ n/p]v+ [n/p^3] + [n/p^4]...


in our case N = 1000 and s is the solution we are looking for.What is the value for P? 10? but the theorem says P must be a prime number and 10 is not prime. But you know what 10 = 2 X 5 also 2 and 5 are prime numbers.
So instead of finding exponents of 10 in 1000!, we can find exponent values of 2 and 5 in 1000! and minimum value will be exponent value of 10 in 1000!
 In other words, if we can find the exponent value of 5 in 1000! we can happily say that many number of zeros will be at the end of 1000!.

Friday, July 29, 2011

Project Euler – Problem1

Problem:

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.Find the sum of all the multiples of 3 or 5 below 1000.

Here is a straight forward solution to this problem,

SELECT SUM(DECODE(MOD(ROWNUM,3),0,ROWNUM,

DECODE(MOD(ROWNUM,5,0,ROWNUM,0)))

FROM DUAL

CONNECT BY LEVEL <1000;

The logic is simple. The CONNECT BY clause in the above statement simply acts as row generator to generate natural numbers from 1 to 999.

The DECODEs inside the aggregate function check whether the number is divisible either by 3 or 5 if so the number is added.

This is a simple solution to understand but certainly not the best when it comes to performance. With the help of mathematical formula this problem can be solved little easier.

Multiples of 3 are 3, 6,9,12 … 999. Sum of them is

3+6+9+…999 = 3 ( 1+2 + … + [999/3]) ( [999/3] denotes integer part of 999/3 )

= 3 ([999/3]) ([999/3]+1)/2 ( 1 + 2+ … + n = n(n+1)/2)

Sum of multiples of 5 is

5 + 10 +15 +…[999/5] = 5([999/5]) ([999/5]+1)/2

The tricky part is the numbers 15, 30 …990 are included in both the case. This series should be subtracted once from the solution. So the final solution is

select trunc(999/3)* (trunc(999/3)+1) *3/2

+ trunc(999/5)* (trunc(999/5)+1) *5/2

- trunc(999/15)* (trunc(999/15)+1) *15/2 from dual;

Answer: 233168

Wednesday, July 27, 2011

SQL query to get last and second last payments to employees

Joe Celko is an American relational database expert. He has participated on the ANSI X3H2 Database Standards Committee, and helped write the SQL-89 and SQL-92 standards. The above lines would explain his innumerable contributions to RDBMS world. His “SQL Puzzles and Answers” is another golden feather on his cap. If you are an SQL geek and you’ve never been come across this book then please try this. I promise you will never be disappointed. Here is a puzzle from this book.

Assume that there is salary table with three columns hold employee name, salary date and salary. This table holds salary information paid to employees. The requirement is to write a query that should return employee’s current and previous salary status for each employee.

You can use the following statement and the pl/sql block to create and populate sample data to test the solutions.

CREATE TABLE emp ( NAME VARCHAR2(50), sal_date DATE, salary NUMBER(15,2))

BEGIN
FOR i IN 1 .. 10
LOOP
INSERT INTO emp
VALUES ('James', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5000 * i);

INSERT INTO emp
VALUES ('Rajendran', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5100 * i);

INSERT INTO emp
VALUES ('Krishna', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5200 * i);

INSERT INTO emp
VALUES ('Jagdish', ADD_MONTHS (TO_DATE(‘01-01-2010’,’DD-MM-YYYY’), i), 5300 * i);


END LOOP;
END;

Here is my first solution to this problem,

SELECT NAME,
(SELECT SUM (salary)
FROM emp emp_inner1
WHERE emp_inner1.sal_date > emp_outer.second_last
AND emp_inner1.NAME = emp_outer.NAME) last_salary,
(SELECT salary
FROM emp e1
WHERE e1.NAME = emp_outer.NAME
AND e1.sal_date = emp_outer.second_last) second_last_salary
FROM (SELECT NAME, MAX (sal_date) second_last
FROM emp emp1
WHERE sal_date < (SELECT MAX (sal_date)
FROM emp emp2
WHERE emp2.NAME = emp1.NAME)
GROUP BY NAME) emp_outer;

I think this is a little expensive query. The main query fetches the second last salary data for each employee. The sub queries in select clause find the last and second last salary by using second last salary date.

But the above query fails when there is a new employee who has got only one payment. The above query does not report the new employee at all. The following solution which looks better than the above also takes care of employees with only one payment.

SELECT NAME,
(SELECT salary
FROM emp emp_inner1
WHERE emp_inner1.sal_date = emp_outer.latest
AND emp_inner1.NAME = emp_outer.NAME) latest,
(SELECT salary
FROM emp emp_inner2
WHERE emp_inner2.sal_date = emp_outer.second_latest
AND emp_inner2.NAME = emp_outer.NAME) second_latest
FROM (SELECT e1.NAME, MAX (e1.sal_date) latest,
MAX (e2.sal_date) second_latest
FROM emp e1, emp e2
WHERE e1.NAME = e2.NAME(+) AND e1.sal_date > e2.sal_date(+)
GROUP BY e1.NAME) emp_outer;

The main query fetches both last and second last payment date using self-outer join. This outer join makes sure that employees with only one payment are not missed out. I'm hoping that I will be updating this post with an even better query one day


Project Euler - An Ideal place to enhance your analytical skills

Think about this, you are in love with analytical problems and you are a software guy and you always feel comfortable when it comes to mathematics. One day you found a website where you have mathematical analytical puzzles and you are expected to solve them using your favorite software tool. Things cannot be better than this. Is in it? I just had the same feeling the moment I came to know the website “Project Euler” through few “siragu muzhaitha paravaigal” (colleagues who put their papers) having quality time with this website

This site completely swept my attention towards it from the moment I saw it. Being a mathematician by nature and software guy by profession, I could not restrict me from solving the puzzles despite a full packed busy schedule.

The objective is simple. Project Euler is a series of challenging mathematical problems. You need to solve them by using any of your favorite programming language in line with the "one-minute rule". This means, your algorithm implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

The “Project Euler” also comes with usual ingredients such as country level ranking, discussion forums, tips to build best algorithm (of course it’s hidden until you post your solution) and many more.

I have chosen interesting software which is not even in the list maintained by Euler Admin itself. Neither have I had any other choice as I know only s/w language since I started my career as IT professional. It is an interesting choice though…It is Oracle SQL and PL/SQL.

People who want to know more before kick-start this just check this link.