Sanstech

Ideas, Knowledge, Technology, Computer Science, Experience associated with my work and some geeky stuff I progressively encounter during my journey towards enlightenment. Read on…

  • RSS RSS Feed

    • The Pragmatic Programmer
      I finished reading The Pragmatic Programmer by Andrew Hunt and David Thomas. It’s not a new book in the market but I was curious to read this. The technology topics covered, are not any different from those found in most software engineering books, but the way they’re presented using Pragmatic Philosophy Approach, is remarkable. Code […]
    • 2013 in review
      The WordPress.com stats helper monkeys prepared a 2013 annual report for this blog. Here’s an excerpt: A San Francisco cable car holds 60 people. This blog was viewed about 1,200 times in 2013. If it were a cable car, it would take about 20 trips to carry that many people. Click here to see the […]
    • Goodbye, Ness!
      It had to happen sometime. I thought Feb 2013 was the right time. I quit Ness after a long 5 years and 4 months of stay, in Feb. I joined FICO (formerly, Fair Isaac) last Feb.  While I get an opportunity to work with many varied stakeholders like Scientists, Architect, Product Management, Peer Developers, PMO, Technical Publications and also […]
    • Meta: information retrieval from Tweets
      I pick significant problems randomly sometimes and enjoy solving them, or at least attempt designing api :-). Here’s one such problem! Problem: How’d you go about finding meta information about a person’s tweets? NOTE: a) Tweet == Twitter updates b) Meta information –> Loosely defined. You can interpret it anyway you want –> Frequency, topics, follower […]
    • Understanding Big Data
      It’s been a while, since I last posted! To keep this rolling (I’m hardly getting any time to post my own articles or stuff about my experiments these days 😦  ), I just wanted to share this ebook on Big Data titled  Understanding Big Data: Analytics for Enterprise Class and Streaming Data. Cheers!
  • Twitter Updates

Pythagorean Triples

Posted by sanstechbytes on July 10, 2011

A quick background on properties of Pythagorean triples can be got from here and here.

When I was browsing through topics in algorithm forum on stackoverflow.com , I found , sort of, an interesting challenge in finding Pythagorean Triples in the given array, saying:  Can’t be achieved in no better than O(n*n) time complexity(a unanimous opinion). This enthused me to attempt writing a faster than O(n*n) algo, but after much analysis and code completion, I couldn’t help joining the participants. In below lines, the code snippet follows. I wonder, if any algorithm enthusiast or researcher could point me to a faster algorithm than O(n*n), if there exists any.

Follow comments in-line to help yourself understand the algorithm used. This algorithm achieves O(k*n*n) time complexity where k is nearly equal to n/3  in most cases. For brevity, it’s an O(n*n) algo.

// O(n+n*log n+k*n*n) = O(k*n*n)= O(n*n) algo where k is nearly n/3 in
// most cases
// Returns the number of triples found.
// Returns
// -1, when n < 3,
// 1 when n = 3 and/or a triple is found and
// 0 when no triple found
public static int pythtriples(int[] pyth) {
int n = pyth.length;

// No duplicate removal algo is used before sort, to avoid the cost of
// O(n),as this will be taken care of below,in for loop.
// (Trivial) Shifting mechanism should be used in
// array with new length in-place(trivial)in case,
// either the element occurring in multiple places is 0 or neg integer

// Square all the numbers – O(n) time complexity.
for (int i = 0; i < n; i++) {
pyth[i] = pyth[i] * pyth[i];
}

// Sort them – O(n * log n) time complexity
Arrays.sort(pyth);

if (n < 3) {
return -1; // error : No of elements must be >= 3
}

// Simple case
if (n == 3) {
if (pyth[2] == pyth[1] + pyth[0])
return 1;
else
return 0;
}

// Compare pair-wise: if(a[i] == (a[j] + a[k]) then, it’s a triple),
// k<i, j<i
// O(k* n * n) time complexity, where k is nearly n/3, can be
int triples = 0, foundtripleLarge = 0;
for (int i = 2; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = i – 1; k >= 0; k–) {
// If already found, don’t compare again for 3SUM. Avoids
// unnecessary check for duplicates
if (foundtripleLarge == pyth[i]) {
break;
}
if (pyth[i] == (pyth[j] + pyth[k])) {
System.out.println(“triples found: ” + pyth[i] + ” = ”
+ pyth[j] + ” + ” + pyth[k]);
triples++; // Counter for triples
foundtripleLarge = pyth[i];
break;
}
}
}
}
return triples;
}

Math: The pair-wise comparison follows: 1^2 + 2^2 + 3^2 + …..+n^2 = n(n+1)(2n+1)/6, nearly equal to 3n^2, same as our O(kn^2) algo above!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
%d bloggers like this: