Vpropel VIT | POD | 07/05/2020 | Smash The Potatoes

Question(Smash_the_potatoes).txt

We have a collection of potatoes, each potato has a positive integer weight.

Each turn, we choose the two heaviest potatoes and smash them together.  Suppose the potatoes have weights x and y with x <= y.  The result of this smash is:

If x = = y, both potatoes are totally destroyed;
If x ! = y, the potato of weight x is totally destroyed, and the potato of weight y has new weight y-x.
At the end, there is at most 1 potato left.  Return the weight of this potato (or 0 if there are no potatoes left.)

Example:-

If the initial weight of the collection is [3,6,2,9,12,7]

We combine 12 and 9 so the array converts to [3,6,2,3,7]

We combine 7 and 6 so the array converts to [3,2,3,1]

We combine 3 and 3 so the array converts to [2,1]

We combine [2,1] so the array converts to [1]

1 is the expected output

Input format:-

N(number of potatoes)

Next n lines weight of the n potatoes

Output format:-

Weight of the last potato remaining

PS:-If you have learnt data structures use of appropriate data structure will be appreciated

Smash_the_potatoes.c

#include<stdio.h>
bool countr(int arr[],int n)
{
    int c=0;
    for(int i=0;i<n;i++)
    {
        if(arr[i]!=0)
            c++;
    }
    if(c<=1)
        return true;
    return false;
}
void Smasher(int arr[],int n)
{
    while(!countr(arr,n))
    {
        int x,y,mx=-1;
        for(int i=0;i<n;i++)
            if(arr[i]>mx)
            {
                mx=arr[i];
                y=i;
            }
        mx=-1;
        for(int j=0;j<n;j++)
        {
            if(j!=y)
            {
                if(arr[j]>mx)
                {
                    mx=arr[j];
                    x=j;
                }
            }
        }
         arr[y]=arr[y]-arr[x];
         arr[x]=0;
    }
}

int main()
{
    int n;
    scanf("%d",&n);
    int arr[n];
    for(int i=0;i<n;i++)
        scanf("%d",&arr[i]);
    Smasher(arr,n);
    for(int i=0;i<n;i++)
        {
            if(arr[i]!=0)
            {
                printf("%d",arr[i]);
                return 0;
            }
        }
    printf("%d",0);
    return 0;
}
//                                              ### Thank YOu :)
//                                                @cs_jawanda
//                                         .Chiranjeet Singh Jawanda.
//                                                VIT VELLORE

Smash_the_potatoes.cpp

#include<iostream>
bool countr(int arr[],int n)
{
    int c=0;
    for(int i=0;i<n;i++)
    {
        if(arr[i]!=0)
            c++;
    }
    if(c<=1)
        return true;
    return false;
}
void Smasher(int arr[],int n)
{
    while(!countr(arr,n))
    {
        int x,y,mx=-1;
        for(int i=0;i<n;i++)
            if(arr[i]>mx)
            {
                mx=arr[i];
                y=i;
            }
        mx=-1;
        for(int j=0;j<n;j++)
        {
            if(j!=y)
            {
                if(arr[j]>mx)
                {
                    mx=arr[j];
                    x=j;
                }
            }
        }
         arr[y]=arr[y]-arr[x];
         arr[x]=0;
    }
}

int main()
{
    int n;
    std::cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
        std::cin>>arr[i];
    Smasher(arr,n);
    for(int i=0;i<n;i++)
        {
            if(arr[i]!=0)
            {
                std::cout<<arr[i];
                return 0;
            }
        }
    std::cout<<0;
    return 0;
}
//                                              ### Thank YOu :)
//                                                @cs_jawanda
//                                         .Chiranjeet Singh Jawanda.
//                                                VIT VELLORE

Smash_the_potatoes.java

import java.util.Scanner;
public class Main
{
     static boolean countr(int arr[],int n)
{
    int c=0,i;
    for(i=0;i<n;i++)
    {
        if(arr[i]!=0)
        {
            c++;
        }
    }
    if(c<=1)
        return true;
    return false;
}

static void Smasher(int[] arr,int n)
    {
        while(!countr(arr,n))
    {
        int x=0,y=0,mx=-1,i,j;
        for(i=0;i<n;i++)
            {if(arr[i]>mx)
            {
                mx=arr[i];
                y=i;
            }
            }
        mx=-1;
        for(j=0;j<n;j++)
        {
            if(j!=y)
            {
                if(arr[j]>mx)
                {
                    mx=arr[j];
                    x=j;
                }
            }
        }
         arr[y]=arr[y]-arr[x];
         arr[x]=0;
    }
    }
    
    public static void main(String[]  arg)
    {
        
        int n;
        Scanner s = new Scanner(System.in);
        n=s.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            {
                arr[i]=s.nextInt();
            }
        Smasher(arr,n);
        for(int i=0;i<n;i++)
        {
            if(arr[i]!=0)
                {
                    System.out.print(arr[i]);
                    return;
                }
        }
        System.out.print(0);
        return;
    }
}
/*------------ALITER

import java.util.Scanner;
class Smash
{
	public boolean countr(int arr[],int n)
	{
	    int c=0,i;
	    for(i=0;i<n;i++)
	    {
	        if(arr[i]!=0)
	        {
	            c++; 
	        }
	    }
	    if(c<=1)
	        return true;
	    return false;
	}
	
	public void Smasher(int[] arr,int n)
    {
        while(!countr(arr,n))
    {
        int x=0,y=0,mx=-1,i,j;
        for(i=0;i<n;i++)
            {if(arr[i]>mx)
            {
                mx=arr[i];
                y=i;
            }
            }
        mx=-1;
        for(j=0;j<n;j++)
        {
            if(j!=y)
            {
                if(arr[j]>mx)
                {
                    mx=arr[j];
                    x=j;
                }
            }
        }
         arr[y]=arr[y]-arr[x];
         arr[x]=0;
    }
    }
}
public class Main
{
    public static void main(String[]  arg)
    {
        
        int n;
        Scanner s = new Scanner(System.in);
        n=s.nextInt();
        int[] arr=new int[n];
        for(int i=0;i<n;i++)
            {
                arr[i]=s.nextInt();
            }
        Smash obj=new Smash();
        obj.Smasher(arr,n);
        for(int i=0;i<n;i++)
        {
            if(arr[i]!=0)
                {
                    System.out.print(arr[i]);
                    return;
                }
        }
        System.out.print(0);
        return;
    }
}

*/

//                                              ### Thank YOu :)
//                                                @cs_jawanda
//                                         .Chiranjeet Singh Jawanda.
//                                                VIT VELLORE

Smash_the_potatoes.py

def countr(arr):
    c=0
    for i in arr:
        if(i!=0):
            c+=1
    if(c<=1):
        return True
    return False

def Smasher(arr,n):
    while countr(arr)==False:
        arr.sort()
        arr[n-2]=abs(arr[n-2]-arr[n-1])
        arr[n-1]=0
       
n= int(input())
arr=[]
for i in range(n):
    arr.append(int(input()))
Smasher(arr,n)
arr.sort(reverse=True);
print(arr[0])

#//                                              ### Thank YOu :)
 #//                                                @cs_jawanda
 #//                                         .Chiranjeet Singh Jawanda.
 #//                                                VIT VELLORE