MATCHSTICK-Editorial

editorial
, ,
1

PROBLEM LINK:

MATCHSTICK

Author: aniket_111
Tester: sahoomirnalin
Editorialist: aniket_111

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Basic mathematics, backtracking, array.

PROBLEM:

Chef is bored at home and only has a matchbox with him. He considers the matches as an integer array containing N matchsticks, where matchsticks[i] is the length of the ith matchstick. Chef wants to use all the matchsticks in the matchbox to make one square. He can’t break any stick, but can link them up, and each matchstick must be used exactly one time.
Return true if chef can make this square and return false otherwise.

EXPLANATION:

Lets see some of the finding from the question.

  1. We need to build a square using all the matchsticks.
  2. As we know,Every side of square is equal.
  3. It means one side length == Parameter Of Square / 4
  • If we carefully observe, parameter == sum of all sides
  • We have given sides information in the form of matchsticks array,
  • So parameter is nothing but Sum(All elements in matchsticks Array).
  • Now the equation become oneSideLength = Sum(All elements in matchsticks Array) / 4

Now from the above points,we can observe that, eachSideLength = TotalSum / 4,
which means we need to divide all the matchsticks into 4 subsets with equal sum.

  1. If you write normal recursion code without pruning then it will fail,
  2. We need to have some pruning steps.
  • If we have choosen one matchstick for 1 side of square then we cannot consider this matchstick for forming other sides.
  • it means if we visit one matchstick then we cannot visit it again.
  • For checking this we can have a boolean array or Bitset, which will tell whether the matchstick element is taken or not.

TIME COMPLEXITY

O(n)

SOLUTIONS:

#include <iostream>
#include <bits/stdc++.h>
#include<vector>
using namespace std;

 bool makesquareHelper(int idx, vector<int>& sides, vector<int>& matchsticks)
    {
        if(idx >= matchsticks.size())
         return sides[0] == sides[1] && sides[1] == sides[2] && sides[3] == 0;
    
      for(int i = 0; i < 4; i++){
          
         if(matchsticks[idx] > sides[i])
             continue;
          
         sides[i] -= matchsticks[idx];
          
         if(makesquareHelper(idx + 1, sides, matchsticks)) 
             return true;
         sides[i] += matchsticks[idx];
      }
      return false;
    }
bool makesquare(vector<int>& matchsticks) {
      if(matchsticks.size() == 0) 
          return false;
      int perimeter = 0;
      for(int i = 0; i < matchsticks.size(); i++){
         perimeter += matchsticks[i];
      }
        
      if(perimeter % 4 !=0) 
          return false;
        
      sort(matchsticks.rbegin(), matchsticks.rend());
        
      int side=perimeter/4;
      vector <int> sides(4,side);
        
      return makesquareHelper(0, sides, matchsticks);
   }
    
   

int main() {
	// your code goes here
	int t,n,a;
	bool f=false;
	cin>>t;
	while(t--){
	    cin>>n;
	    vector<int> v;
	    for(int i=0;i<n;i++){
	        cin>>a;
	        v.push_back(a);
	    }
	    f=makesquare(v);
	    if(f)
	    cout<<"true"<<endl;
	    else 
	    cout<<"false"<<endl;
	}
	return 0;
}