Vpropel VIT | POD | 19/05/2020 | Chalk sticks | 14

chalk_sticks.cpp

#include<iostream>
#include<algorithm>
#include<numeric>
#include<sstream>
#include<string>
#include<vector>
using namespace std;

bool sqmaker(std::vector<int> &v)
{
    int side[4]={0};
    int eachS=std::accumulate(v.begin(),v.end(),0);
    if(eachS%4!=0)  return false;
    else    eachS=eachS/4;
    bool checker[v.size()]={false};
    for(int i:v) if(i>eachS) return false;
    for(int i=0;i<4;i++)
    {
        for(int j=0;j<v.size();j++)
            if(side[i]+v[j]<=eachS && checker[j]==false)
            {
                side[i]+=v[j];
                checker[j]=true;
            }
        if(side[i]!=eachS) return false;
    }
    return true;
}

int main()
{
    int  n;
    std::cin>>n;
    std::vector<int> v;
    std::string str;
    std::cin>>str;
    std::stringstream s(str);
    while(s.good())
    {
        std::string temp;
        std::getline(s,temp,',');
        std::stringstream s_temp(temp);
        int k;
        s_temp>>k;
        v.push_back(k);
    }

    std::sort(v.begin(),v.end());
    std::reverse(v.begin(),v.end());
    if(sqmaker(v))
        std::cout<<"Yes";
    else
        std::cout<<"No";
}
//                                          ### Thank YOu :) 
//                                            @cs_jawanda
//                                     .Chiranjeet Singh Jawanda.
//                                            VIT VELLORE

chalk_sticks.java

import java.util.Scanner;
import java.util.Arrays;
class solve
{
    boolean makesquare(int v[])
    {
        Arrays.sort(v);
        reverse(v);
        int side[]=new int[4];
        int eachS=0;
        for(int i:v) eachS+=i;
        if(eachS%4!=0)  return false;
        else    eachS=eachS/4;
        boolean checker[]=new boolean[v.length];
        for(int i:v) if(i>eachS) return false;
        for(int i=0;i<4;i++)
        {
            for(int j=0;j<v.length;j++)
                if(side[i]+v[j]<=eachS && checker[j]==false)
                {
                    side[i]+=v[j];
                    checker[j]=true;
                }
            if(side[i]!=eachS) return false;
        }
        return true;
    }   
   private void reverse(int[] nums) 
   {
       int i = 0, j = nums.length - 1;
       while (i < j) 
       {
           int temp = nums[i];
           nums[i] = nums[j];
           nums[j] = temp;
           i++; j--;
       }
    }
}
public class Main
{
    public static void main(String []args) throws Exception
    {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
       String str=s.next();
        String []nums=str.split(",");
        int number[]=new int[n];
        for(int i=0;i<n;i++)
            number[i]=Integer.parseInt(nums[i]);
        solve obj=new solve();
        if(obj.makesquare(number))
            System.out.print("Yes");
        else 
            System.out.print("No");
    }
}
//                                          ### Thank YOu :) 
//                                            @cs_jawanda
//                                     .Chiranjeet Singh Jawanda.
//                                            VIT VELLORE

chalk_sticks.py

def sqMaker(v):
    eachS=sum(v)
    if eachS%4!=0:
        return False;
    else:
        eachS=eachS//4
    sides=[0,0,0,0]
    checker=[False]*len(v)
    for i in range(4):
        for j in range(len(v)):
            if (sides[i]+v[j]<=eachS and checker[j]==False):
                sides[i]+=v[j]
                checker[j]=True
        if sides[i]!=eachS:
            return False
    return True
    
n=int(input())
v=input().split(',')
v=[int(x) for x in v]
v.sort(reverse=True)
if sqMaker(v):
    print("Yes")
'''
//                                              ### Thank YOu :) 
//                                                @cs_jawanda
//                                         .Chiranjeet Singh Jawanda.
//                                                VIT VELLORE
'''

chalk_sticks2.java

//Using DFS
import java.util.Scanner;
import java.util.Arrays;
class solve
{
    public boolean makesquare(int[] nums) 
    {
        if (nums == null || nums.length < 4) return false;
           int sum = 0;
           for (int num : nums) sum += num;
           if (sum % 4 != 0) return false;
           Arrays.sort(nums);
           reverse(nums);
           
        return dfs(nums, new int[4], 0, sum / 4);
    }
       
   private boolean dfs(int[] nums, int[] sums, int index, int target) 
   {
        if (index == nums.length) 
        {
            if (sums[0] == target && sums[1] == target && sums[2] == target) 
            {
         return true;
            }
        return false;
        }
        
        for (int i = 0; i < 4; i++) 
        {
            if (sums[i] + nums[index] > target) continue;
            sums[i] += nums[index];
               if (dfs(nums, sums, index + 1, target)) return true;
            sums[i] -= nums[index];
        }
        
        return false;
    }
       
    private void reverse(int[] nums) 
    {
       int i = 0, j = nums.length - 1;
       while (i < j) 
       {
           int temp = nums[i];
           nums[i] = nums[j];
           nums[j] = temp;
           i++; j--;
       }
    }
}
public class Main
{
    public static void main(String []args) throws Exception
    {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
       String str=s.next();
        String []nums=str.split(",");
        int number[]=new int[n];
        for(int i=0;i<n;i++)
            number[i]=Integer.parseInt(nums[i]);
        solve obj=new solve();
        if(obj.makesquare(number))
            System.out.print("Yes");
        else 
            System.out.print("No");
    }
}
// External source :)

chalk_sticks3.java

// DP

import java.util.Scanner;
import javafx.util.Pair;
import java.util.HashMap;
class solve {

      HashMap<Pair<Integer, Integer>, Boolean> memo;

      int[] nums;

      int possibleSquareSide;

     solve() {
        memo = new HashMap<Pair<Integer, Integer>, Boolean>();
    }

     boolean recurse(Integer mask, Integer sidesDone) {
        int total = 0;
        int L = this.nums.length;

        Pair<Integer, Integer> memoKey = new Pair(mask, sidesDone);

        for(int i = L - 1; i >= 0; i--) {
            if ((mask&(1 << i)) == 0) {
                total += this.nums[L - 1 - i];
            }
        }

         if (total > 0 && total % this.possibleSquareSide == 0) {
            sidesDone++;
        }

        if (sidesDone == 3) {
            return true;
        }

        if (this.memo.containsKey(memoKey)) {
            return this.memo.get(memoKey);
        }

        boolean ans = false;
        int c = total / this.possibleSquareSide;

        int rem = this.possibleSquareSide * (c + 1) - total;

        for(int i = L - 1; i >= 0; i--) {
            if (this.nums[L - 1 - i] <= rem && (mask&(1 << i)) > 0) {
                if (this.recurse(mask ^ (1 << i), sidesDone)) {
                    ans = true;
                    break;
                }
            }
        }

        this.memo.put(memoKey, ans);
        return ans;
    }

     boolean makesquare(int[] nums) {

        if (nums == null || nums.length == 0) {
            return false;
        }

        int L = nums.length;
        int perimeter = 0;
        for(int i = 0; i < L; i++) {
            perimeter += nums[i];
        }

        int possibleSquareSide =  perimeter / 4;
        if (possibleSquareSide * 4 != perimeter) {
            return false;
        }

        this.nums = nums;
        this.possibleSquareSide = possibleSquareSide;
        return this.recurse((1 << L) - 1, 0);
    }
}
public class Main
{
    public static void main(String []args)
    {
    	Scanner s=new Scanner(System.in);
        int n=s.nextInt();
       String str=s.next();
        String []nums=str.split(",");
        int number[]=new int[n];
        for(int i=0;i<n;i++)
            number[i]=Integer.parseInt(nums[i]);
        solve obj=new solve();
        if(obj.makesquare(number))
            System.out.print("Yes");
        else 
            System.out.print("No");
    }
}
// External source :)

chalk_sticks4.java

//Using DFS(2nd method)
import java.util.Scanner;
import java.util.Arrays;
class solve
{
	public boolean makesquare(int[] nums)
	{
		int sum=0;
		for(int num: nums) sum+=num;
		if(sum%4!=0) return false;
		Arrays.sort(nums);
		return dfs(nums,0,sum/4,0,1,new boolean[nums.length]);
	}
	private boolean dfs(int []nums,int tempSum, int target,int pos,int groupId,boolean[] visited)
	{
		if(groupId==4) return true;
		if(target==tempSum)  return dfs(nums,0,target,0,groupId+1,visited);
		if(target<tempSum) return false;
		for(int i=pos;i<nums.length;i++)
		{
			if(visited[i]) continue;
			if(i>0 && nums[i]==nums[i-1] && !visited[i-1]) continue;
			visited[i]=true;
			if(dfs(nums,tempSum+nums[i],target,i+1,groupId,visited)) return true;
			visited[i]=false;
		}
		return false;
	}
	
}
public class Main
{
    public static void main(String []args) throws Exception
    {
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
       String str=s.next();
        String []nums=str.split(",");
        int number[]=new int[n];
        for(int i=0;i<n;i++)
            number[i]=Integer.parseInt(nums[i]);
        solve obj=new solve();
        if(obj.makesquare(number))
            System.out.print("Yes");
        else 
            System.out.print("No");
    }
}
// External source :)

Question(chalk_sticks).txt

Chalk sticks
Ganesh has n chalk sticks of various lengths. He tries to build a square out of the chalk sticks he have. Given the length of n chalk sticks check whether he can build a square or not. Every chalk stick must be used

Example:-

Input:- [1,1,2,2,2]

Output:-Yes

Explanation:-As square of side length 2 can be formed from the given lengths

Example:-

Input: [3,3,3,3,4]

Output: No

Explanation: You cannot find a way to form a square with all the matchsticks.

Input format:-

n-number of chalk sticks

Length of n chalk sticks separated by comma

Output format:-

Yes/No

https://leetcode.com/articles/matchsticks-to-square/