Algorithm to find the 2 largest numbers smaller than 2 integers a and b, that are divisible by each other.
So here’s the challenge. Given 2 integers named a and b:

// Find the 2 largest numbers, smaller than a and b, that are divisible by each other.

// input: a:102,b:53 
// output: (100,50)
			
// input: a:7,b:4 
// output: (6,3)
			
// input: a:3,b:2 
// output: (2,2)

The catch is, I don’t want to brute force it. I think it comes out to O(n²).

Here’s the signature for the method:

<pre>
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
}
</pre>

Here’s a sample implementation:

<pre>
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;
}
</pre>

Here’s the test client:

<pre>
class Program
{
	static void Main(string[] args)
    {
		Console.WriteLine(Analyze(102, 53));
		Console.WriteLine(Analyze(6, 4));
		Console.WriteLine(Analyze(3, 2));
	}
}
</pre>

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?

Algorithm to find the 2 largest numbers smaller than 2 integers a and b, that are divisible by each other.
===

So here’s the challenge. Given 2 integers named a and b:

// Find the 2 largest numbers, smaller than a and b, that are divisible by each other.

// input: a:102,b:53 
// output: (100,50)
			
// input: a:7,b:4 
// output: (6,3)
			
// input: a:3,b:2 
// output: (2,2)

The catch is, I don’t want to brute force it. I think it comes out to O(n²).

Here’s the signature for the method:

<pre>
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
}
</pre>

Here’s a sample implementation:

<pre>
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;
}
</pre>

Here’s the test client:

<pre>
class Program
{
	static void Main(string[] args)
    {
		Console.WriteLine(Analyze(102, 53));
		Console.WriteLine(Analyze(6, 4));
		Console.WriteLine(Analyze(3, 2));
	}
}
</pre>

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?
