Find Remaining Volume of the Last Cloud | Cloud Smashing Game

Given an array of N integers, where each value represents the volume of the cloud. The task is to choose the two highest volume clouds from an array and smash them together. When two clouds smash then the clouds get condense into water and it rains. If the two highest volume cloud is not equal then the volume of the highest volume cloud becomes the subtraction of the two chosen clouds. You are supposed to do it till the count of clouds becomes at most one.

Now, let the two highest volume clouds be chosen to be A and B:

If A>B: The cloud with less volume i.e. B will get destroyed and the volume of A changed to A-B.
If A==B: Both clouds will get condensed with no remaining.

Now do this with all the clouds and finally at most a single or 0 clouds will be left. Return the volume of that cloud left. If No cloud is left then return 0.

Example:

There are 6 clouds with their volume in a list is given. Let the volume of the clouds be clouds[ ] = {3, 5, 9, 2, 8, 2}.
So the Last cloud left would be the one with the volume one.

Explanation:

No. of clouds, N = 6
CloudsVolume = {3,5,9,2,8,2}
In 1st iteration => Maxvolume of two Clouds S1=9 & S2=8
Thus remaning = 9-8 = 1
Thus remaning Clouds= {3,5,1,2,2}

2nd iteration => Maxvolume of two Clouds S1=5 & S2=3
Thus remaning = 5-3 = 2
Thus remaning Clouds = {2,1,2,2}

3rd iteration => Maxvolume of two Clouds S1=2 & S2=2
Thus remaning = 2-2 = 0
Thus remaning Clouds = {2,1}

4th iteration => Maxvolume of two Clouds S1=2 & S2=1
Thus remaning = 2-1 = 1
 
Thus last Cloud=> 1

Approach-1: Using sorting at each iteration

A simple solution of it can be to sort the Clouds’ Volume array in ascending order and iteratively find the solution.

Step-1: Sort the clouds’ volume array in ascending order
Step-2: Initialize a pointer ‘i’ that travels from left to right with 0. Within the loop follow steps 3 to 4 till i<size of clouds array.
Step-3: For each iteration check the last 2 positions of the array and subtract them.
Step-4: If the difference is greater than 0 then replace the second max element with 0 and maximum element with the given subtraction. Increase i to i+1.
Step-5: If the difference is 0 then replace both the elements with -1.
Step-6: Again sort the array.
Step-7: Return clouds[size-1].

Iteration in Algorithm:

Clouds after sorting => 2 2 3 5 8 9 
diff= 9-8 = 1 => replace 8<->-1  and 9<->1 

2nd iteration: -1 1 2 2 3 5 
3rd iteration: -1 -1 1 2 2 2 
4th iteration: -1 -1 -1 -1 1 2 
5th iteration: -1 -1 -1 -1 -1 1

Return arr[size-1] == 1

Implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int lastCloudVolume(vector < int > & clouds) {
  int size = clouds.size();
  // If there is only one cloud 
  // then return that cloud 
  if (size <= 1) {
    return clouds[0]; 
  }

  // Sort the volume of clouds 
  sort(clouds.begin(), clouds.end()); 

  // Iterator for the end condition of the loop
  int i = 0;  
  while (i < size - 1 && (clouds[size - 2] > 0 || clouds[size - 1] != 0)) {

    int max1 = clouds[size - 1]; // max volume  cloud 
    int max2 = clouds[size - 2]; // 2nd max volume cloud 
    int remaining = max1 - max2; // remaining volume  

    // If volume is greater than 1, 
    // then the elements mentioned in step 3
    if (remaining > 0) 
    {
      clouds[size - 1] = remaining;
      clouds[size - 2] = -1;
      i++;
    } else // else replace with -1
    {
      clouds[size - 1] = -1;
      clouds[size - 2] = -1;
      i += 2;
    }

    sort(clouds.begin(), clouds.end()); // Again sort 
  }

  // If whole matrix is filled with -1 then return 0,
  // as no clouds left to mash else return last element stored 
  return clouds[size - 1] == -1 ? 0 : clouds[size - 1]; 
}

int main() {
  vector<int> CloudsVolume ={3,5,9,2,8,2};
  cout << "Last remaining cloud: " << lastCloudVolume(CloudsVolume);
  return 0;
}

Java

import java.io.*;
import java.util.*;

public class Cpp {
  public static int lastCloudVolume(ArrayList<Integer> clouds) {
    int size = clouds.size();
    // If there is only one cloud
    // then return that cloud
    if (size <= 1) {
      return clouds.get(0);
    }

    // Sort the volume of clouds
    Collections.sort(clouds);

    // Iterator for the end condition of the loop
    int i = 0;
    while (i < size - 1 && (clouds.get(size - 2) > 0 || clouds.get(size - 1) != 0)) {

      int max1 = clouds.get(size - 1); // max volume cloud
      int max2 = clouds.get(size - 2); // 2nd max volume cloud
      int remaining = max1 - max2;     // remaining volume

      // If volume is greater than 1,
      // then the elements mentioned in step 3
      if (remaining > 0) {
        clouds.set(size - 1, remaining);
        clouds.set(size - 2, -1);
        i++;
      } else // else replace with -1
      {
        clouds.set(size - 1, -1);
        clouds.set(size - 2, -1);
        i += 2;
      }

      Collections.sort(clouds); // Again sort
    }

    // If the whole matrix is filled with -1, then return 0
    // as no clouds left to mash else return the last element stored
    return clouds.get(size - 1) == -1 ? 0 : clouds.get(size - 1);
  }

  public static void main(String[] args) {
    ArrayList<Integer> cloudvolume = new ArrayList<>();
    cloudvolume.add(3);
    cloudvolume.add(5);
    cloudvolume.add(9);
    cloudvolume.add(2);
    cloudvolume.add(8);
    cloudvolume.add(2);
    System.out.println("Last remaining cloud: " + lastCloudVolume(cloudvolume));
  }
}

Output:

Last remaining cloud: 1

Time and Space Complexity of the Sorting at each interval approach:

Time complexity: O(n*(n*logn)).
Here, n = number of clouds given. 
For n number of times, we are sorting our volume list. 
Thus sorting O(nlogn) and n times.

Space Complexity: O(1)

Approach-2: Optimised using Priority Queue/ Max heap

In the previous approach, we required O(nlogn) time for sorting in each interval.
This can get improved by using priority queue/ Max heap. Heap takes O(logN) time for insertion as well as deletion.

Below are the steps mentioned:

Step-1: Create a heap and heapify all the clouds’ volume in the heap.
Step-2: Now run a loop which continues till N=heap.size()>=1
Step-3: Now pop 2 elements as Max1 and Max2. Store the Difference of Max1-Max2. Also, decrease the N by 2.
Step-4: If the difference is greater than 0 then push the difference into a heap and increase the count of N by 1. Else continue.
Step-5: If the heap is not empty then return maxheap.top(). Else return 0.

Example Explanation:

No. of clouds, N = 6
CloudsVolume = {3,5,9,2,8,2}
After heapify CloudsVolume = {9,8,5,3,2,2)
In 1st iteration => Maxvolume of two clouds S1=9 & S2=8
Thus remaning = 9-8 = 1

Insert 1 => {5,3,2,2,1)
2nd iteration => Maxvolume of two clouds S1=5 & S2=3
Thus remaning = 5-3 = 2

Insert 2 => {2,2,2,1)
3rd iteration => Maxvolume of two clouds S1=2 & S2=2
Thus remaning = 2-2 = 0
Insert nothing => {2,1)
 
4th iteration => Maxvolume of two clouds S1=2 & S2=1
Thus remaning = 2-1 = 1
Insert 1 => {1}
 
return 1;

Implementation of the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

int lastCloudVolume(vector < int > & clouds) {

  priority_queue < int > max_heap;
  int size = clouds.size();

  // Heapify all the clouds volume 
  for (int i = 0; i < size; ++i)
    max_heap.push(clouds[i]);

  // Max1 = Maximum, Max2 = 2nd Maximum
  int Max1, Max2; 

  while (size > 1) {
    Max1 = max_heap.top();
    max_heap.pop(); // Pop the maxmimum
    Max2 = max_heap.top();
    max_heap.pop(); // Pop the second maximum
    size -= 2; // Decrease the size of heap by 2, as 2 elements popped 

    // if remaining clouds volume >0
    // the push that remaining cloud in heap
    if (Max1 - Max2 > 0) 
    {
      max_heap.push(Max1 - Max2);
      size += 1; // Increament size of heap by 1
    }
  }

  // If heap is not empty, 
  // then return the last element/cloud left 
  if (!max_heap.empty()) 
    return max_heap.top();

  return 0; //else return 0
}

int main() {
  vector<int> Cloudvolume ={3,5,9,2,8,2};
  cout << "Last remaining cloud: " << lastCloudVolume(Cloudvolume);
  return 0;
}

Java

import java.util.*;

public class Cpp {
    public static int lastCloudVolume(ArrayList<Integer> clouds) {
        PriorityQueue<Integer> max_heap = new PriorityQueue<Integer>(Collections.reverseOrder());
        int size = clouds.size();

        // Heapify all the cloud volume
        for (int i = 0; i < size; ++i)
            max_heap.add(clouds.get(i));

        // Max1 = Maximum, Max2 = 2nd Maximum
        int Max1, Max2;

        while (size > 1) {
            Max1 = max_heap.poll(); // Pop the maximum
            Max2 = max_heap.poll(); // Pop the second maximum
            size -= 2; // Decrease the size of heap by 2, as 2 elements popped

            // If remaining clouds' volume > 0,
            // then push that remaining cloud in the heap
            if (Max1 - Max2 > 0) {
                max_heap.add(Max1 - Max2);
                size += 1; // Increment size of the heap by 1
            }
        }

        // If the heap is not empty,
        // then return the last element/cloud left
        if (!max_heap.isEmpty())
            return max_heap.peek();

        return 0; // else return 0
    }

    public static void main(String[] args) {
        ArrayList<Integer> cloudvolume = new ArrayList<>();
        cloudvolume.add(3);
        cloudvolume.add(5);
        cloudvolume.add(9);
        cloudvolume.add(2);
        cloudvolume.add(8);
        cloudvolume.add(2);
        System.out.println("Last remaining cloud: " + lastCloudVolume(cloudvolume));
    }
}

Output:

Last remaining cloud: 1

Time and Space Complexity of the MaxHeap approach:

Time complexity: O(nlogn)
Here n = number of clouds given. 
For pushing and popping elements into Maxheap it requires O(logn) time and we are doing it at most n times.

Space Complexity: O(n)
Maxheap will be of size n.

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.