CPP: Largest Possible Square

Solution for the Largest Possible Square problem in Cpp

Problem Description

You have to construct the Largest Possible Square

  • You have two wooden sticks:
  • One of length A
  • One of length B
  • You are allowed to cut each stick into smaller pieces, but:
  • Each piece must have an integer length
  • You can leave leftover wood unused
  • Your goal is to build a square, which means:
  • You need exactly 4 sticks
  • All 4 sticks must have the same length
  • Return the maximum possible length of the square’s side.
  • If it’s impossible to get 4 equal sticks → return 0.

Solution

cpp 
// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int count_pieces(int length, int stick1, int stick2) {
	return (stick1 / length) + (stick2 / length);
}

bool can_form_square(int length, int stick1, int stick2) {
	return count_pieces(length, stick1, stick2) >= 4;
}

int solution(int A, int B) {
    for (int length = (A + B) / 4; length > 0; length--) {
        if (can_form_square(length, A, B)) {
            return length;
        }
    }
    return 0;
}