StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAlgorithm to find the 2 largest numbers smaller than 2 integers a and b, that are divisible by each other
text
Body
copied!<p>So here’s the challenge. Given 2 integers named a and b:</p> <p>// Find the 2 largest numbers, smaller than a and b, that are divisible by each other.</p> <p>// input: a:102,b:53 // output: (102,51)</p> <p>// input: a:7,b:4 // output: (6,3)</p> <p>// input: a:3,b:2 // output: (2,2)</p> <p>The catch is, I don’t want to brute force it. I think it comes out to O(n²).</p> <p>Here’s the signature for the method:</p> <pre><code>static Tuple<int, int> Analyze(int a, int b) { if (a % b == 0) return new Tuple<int, int>(a, b); else // Here’s where the algorithm kicks in } </code></pre> <p>Here’s a sample implementation:</p> <pre><code>static Tuple<int, int> Analyze(int left, int right) { if (left % right == 0) return new Tuple<int, int>(left, right); else { for (int i = left; i >= right; i--) { for (int j = right; j >= 0; j--) if (i % j == 0) return new Tuple<int, int>(i, j); else i--; } } return null; } </code></pre> <p>Here’s the test client:</p> <pre><code>class Program { static void Main(string[] args) { Console.WriteLine(Analyze(102, 53)); Console.WriteLine(Analyze(6, 4)); Console.WriteLine(Analyze(3, 2)); } } </code></pre> <p>There are obviously problems with my implementation, but it’s not bad for starters. For instance when I use 106 and 54 for my arguments, had I not decremented the outter loop variable (i-- in the else block), I’d have found a match with 106 and 53. Instead I find a match a 104 and 52, which isn’t quite right but is relatively close to the desired result. However, my sample implementation is much faster than a brute forced approach because I’d never loop anymore than b times, making it O(b). Thoughts, inputs?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload