Practice 1

27 Mar 2014

For this practice I completed problem 1.19 from the Data Structures and Problem Solving using Java book. This book is a bit old, but is still a great resource for brushing up on Java and solving some interesting problems (and the best part being that I already owned it :) ). Of course, all of the source code for the problem is available on Github

The Problem

Write a program to determine all pairs of positive integers (a,b) such that a < b < 1000 and (a2+b2+1)/(ab) is an Integer.

Solution

This was a pretty simple problem, pretty much just:

  • Loop up to 1000 setting value to b
  • Loop up to the current value of b setting the value to a
  • Run the calculation (a2+b2+1)/(ab) for current values of a and b
  • Check if the current value from the calculation is an integer using a cast and compare with the current value.

Java

Ruby

Analysis

Because the solution requires us to loop through all values for a up to b and all values of b up to 1000 the loop will always be exhaustive. The check for whether this value is an integer is negligible in comparison to these loops so it does not need to be factored in for worst case analysis. This results in us having a Big O performance of O(n2) or quadratic. This is not the greatest runtime in the world since the runtime will increase pretty rapidly if we were to increase the maximum number for the value (in this case 1000).

Thats all for now, happy coding!

comments powered by Disqus