Modifying the Euler Totient Funtion

Hi All, Came across an interesting problem and thought of sharing it. Most would know about the ETF , which basically helps one to count the number of integers co-prime and less than N . However to get the count of integers which are co-prime to N but less than a specified limit (say M <= N ) is not so common.

At first i thought of modifying the ETF calculation ETF calculation by initialising result to m . The results were 'almost' accurate but not correct. So as a turnaround , i got a different approach. We can factorise N and then from M do an inclusion-exclusion principle on the factors of N . i.e say the factors of N are p1,p2,p3..pk . Then the required solution would be : M - sum(M/pi) (1<=i<=k) + sum(M/pi*pj) - ..sum(M/pi*pj*..pk)

Though i had got the result but coding it was the next challenge. 1. First step was easy as it involved just factoring N . (O(sqrt(N)))
2. Next we had to get all combinations of the factors, in other words all the subsets. This can be done by bitmask technique, i.e consider binary representation of integers and if the ith bit is set then the integer is in the set . We can store each subset in a vector and then based on the size of the subset calculate the denominator with appropriate sign!
3. Thus we can calculate the answer perfectly. :)

Hope it was useful. Finally a post after almost 6 months.Been really busy , specially after getting into this corporate world.

A tutorial on trees

I came across this site eternally confuzzled which seems really good on data structures, specially trees and thought of sharing it..Hope it's useful :)

divisibility by 7

Hi, recently i came across a problem where it was required to check if a number is divisible by 7 . Though quiet an elementary task, i think its not very commonly known. This is what i found.
Test 1:
Reverse the number . Mulitply each digit of this reversed number by the digits 1(=1%7),3(=10%7),2(=100%7),6(=1000%7),4(=10000%7),5(=100000%7) consequtively till all digits are covered. Sum the products. If this value is divisible by 7 then the original number is too.
Actually these numbers are the cyclic remainders of division by 7.
Test 2:
Take the last digit of the number and subtract it from the number formed by the remaining digits.If this value is divisible by 7 then the original number is too. We can do it recursively to reduce the number .

Hope that helps.

Pointers

Hi, recently came across an article which through some questions, has great explanation of pointers . They show that arrays are not pointers which is common pitfall.
Here's the link:
Pointers
Njoy reading. :)

Adding Javadoc of a jar in eclipse

Hi, recently i was facing with this problem of how to add the javadoc files of a jar in eclipse. I used netbeans earlier in which it was a simple process but here its not so straightforward.
First go to configure build-path of the project and select the jar in libraries tab. On expanding the jar file add the javadoc location to it and you'r done.
Hope its hopeful.

Some pearls of wisdom

Recently i came across few articles which were very inspiring especially for programmers.
They generally are concerned about how one must learn a language, start programming and ask relevant questions
Here are the links:

How to ask the smart way
Short simple examples
Why everyone's in a rush?

Hope it was useful.

Finding the shortest distance connecting 3 points

I came across another interesting problem, THREETW1 in spoj, thanks to hwk . Here we need to calculate the co-ordinates of the point which connects 3 points in shortest path.
For this problem we need to find the Fermat point . We first calculate the barycenter of this point from the sides of the triangle and then represent it in cartesian form.
This problem has application in finding the point where 3 points would be linked most efficiently , specially in cable wires and telephones.
Happy coding!!