Monday, May 15, 2006

Simple, Yet Annoying Coding Problem

Here's a simple coding problem. What I'm looking for is a simple and efficient solution that does not require any loops. My current solution is pretty efficient, but I think there are probably better solutions, so I will pose the problem here.

IP Addresses are of the form: A.B.C.D where A, B, C, D range from 0 to 255. A computer stores an IP Address as a single value. So, an IP of 0.0.0.0 = 0, an IP of 0.0.1.0 = 256, and an IP of 0.0.2.5 = 517. An IP is simply a base-256 number.

So, say you were given an X and a Y (Y >= X). How many IPs are contained in the range INCLUSIVE that do not end with a 0 or a 255?

Here are some sample Inputs and Outputs (X,Y) --> Total.

(0, 256) --> 254
(250, 255) --> 5
(500, 1000) --> 497
(123, 99999) --> 99097

Anyone have a clever, efficient, coding solution? I'll post mine up in a few days.

*** Edit ***

I now have a solution without any conditionals. So it is a straight formula with the terms X and Y. The formula is pretty ugly, but at least it's a straight (and fast) computation.

1 comment:

Brute Force said...

Total = (254 * (Y/256 - X/256 - 1)) + (255 - (X % 256)) + (Y % 256) - (((Y % 256) + 1)/256) -((256 - (X % 256))/256)

Note that the above is using all integer math. Anyway, the computation should be fast since there's a lot of powers of 2.

Quantcast