🔗 Failure Rate

Super game developer Aurely has fallen into a deep worry. Her game Friends Ochunsung was a huge success, but lately the number of new users has plummeted. The cause was that the stage gap between new users and existing users was too large.

Pondering how to solve this problem, she decided to adjust the difficulty by dynamically extending playtime. Being a super developer, she implemented most of the logic easily, but ran into a crisis when it came to calculating the failure rate. Complete the code that calculates the failure rate for Aurely.

• The failure rate is defined as follows.
  • (Number of players who reached the stage but have not yet cleared it) / (Number of players who reached the stage)

Given the total number of stages N and an array stages containing the stage number each current player is stuck on, complete the solution function so that it returns an array of stage numbers sorted in descending order of failure rate.

• The total number of stages N is a natural number between 1 and 500.
• The length of stages is between 1 and 200,000.
• stages contains natural numbers between 1 and N + 1.
  • Each natural number represents the stage number the user is currently attempting.
  • However, N + 1 represents a user who has cleared all the way through the last stage (stage N).
• If multiple stages have the same failure rate, the stage with the smaller number should come first.
• If no user has reached a stage, that stage's failure rate is defined as 0.

Input/Output Example #1

A total of 8 users attempted stage 1, and of those, 1 user has not yet cleared it. So the failure rate for stage 1 is as follows.

• Stage 1 failure rate: 1/8

A total of 7 users attempted stage 2, and of those, 3 users have not yet cleared it. So the failure rate for stage 2 is as follows.

• Stage 2 failure rate: 3/7

Likewise, the failure rates for the remaining stages are as follows.

• Stage 3 failure rate: 2/4
• Stage 4 failure rate: 1/2
• Stage 5 failure rate: 0/1

Sorting the stage numbers by descending failure rate gives the following.

• { 3, 4, 2, 1, 5 }

Input/Output Example #2

Since every user is on the last stage, stage 4's failure rate is 1 and the failure rate of the remaining stages is 0.

• { 4, 1, 2, 3 }

This problem asks us to compute the failure rate of each stage. We find the number of people who attempted each stage and the number who failed it. The goal is to use this information to compute the failure rates, sort by failure rate, and return the result.

If you don't read the problem carefully, you might end up dividing by the total number of people instead of the number of people who reached that stage, so be careful.

1. Count the number of people currently sitting on each stage.
2. Count the number of people who played each stage.
   • If someone is sitting on stage 4, they attempted stages 1 through 4, and this is reflected in stage 4's failure rate.
   • For stage N + 1, since it means they cleared everything, it counts as attempting every stage.
3. Compute the failure rate as (people stuck on the stage) / (people who played the stage) * 100.
4. Sort by failure rate and return the stage numbers.
   • If failure rates are equal, sort by stage number.

The above flow works well.

Steps 1 and 2 aren't hard to implement by iterating over stages. Create integer arrays fails and users of length N to count the number who failed and the number who attempted, respectively.

JAVA
int[] fails = new int[N];
int[] users = new int[N];

// Count attempters and failures
for (int stage : stages)
{
	// If the last stage was not cleared
	if (stage != N + 1)
	{
		// Count the failed user
		fails[stage - 1]++;
		
		// Count the attempted users
		for (int i = 0; i < stage; i++)
		{
			users[i]++;
		}
	}
	
	// If the last stage was cleared
	else
	{
		// Count all attempted users
		for (int i = 0; i < users.length; i++)
		{
			users[i]++;
		}
	}
}

Note that if someone is sitting on stage 4, it's actually stored in fails[3], so make sure to reflect this via fails[stage - 1].

Step 3 is just a simple calculation, but step 4 is the tricky part. What actually needs to be returned isn't the failure rate itself but the stage number that has that failure rate.

To make sorting convenient, declare an ArrayList<Double[]> and manage the stage number and failure rate together as an array.

The failure rate can be computed as (number of people who failed the stage) / (number of people who attempted the stage). However, if nobody has reached the stage, this results in dividing by 0, so this must be handled with the isNaN() method.

For example, take N = 5, [ 1, 2, 2, 3, 4 ]. For stage 5, nobody even attempted it, so the failure rate becomes 0 / 0, which is NaN. So in this case, it must be converted to 0.

JAVA
// Failure rate
ArrayList<Double[]> failRate = new ArrayList<>();

// Assign index and value to the failure rate
for (int i = 0; i < N; i++)
{
	// If there are no attempters or failures, this divides by 0, so NaN handling is needed
	double rate = Double.isNaN((double) fails[i] / users[i]) ? 0 : (double) fails[i] / users[i];
	
	failRate.add(new Double[] { (double) i + 1, rate });
}

Store an array containing the stage number and failure rate in failRate.

JAVA
// Sort
failRate.sort((o1, o2) -> Double.compare(o2[1], o1[1]));

The sort is as shown above. Since sort() defaults to ascending order, we need to specify a separate comparison to sort in descending order.

JAVA
import java.util.ArrayList;

/**
 * Failure Rate class
 *
 * @author RWB
 * @since 2021.12.11 Sat 02:20:18
 */
class Solution
{
	/**
	 * Method that returns the answer
	 *
	 * @param N: [int] total number of stages
	 * @param stages: [int[]] current stage numbers
	 *
	 * @return [int[]] stages with the highest failure rate
	 */
	public int[] solution(int N, int[] stages)
	{
		int[] fails = new int[N];
		int[] users = new int[N];
		
		// Count attempters and failures
		for (int stage : stages)
		{
			// If the last stage was not cleared
			if (stage != N + 1)
			{
				// Count the failed user
				fails[stage - 1]++;
				
				// Count the attempted users
				for (int i = 0; i < stage; i++)
				{
					users[i]++;
				}
			}
			
			// If the last stage was cleared
			else
			{
				// Count all attempted users
				for (int i = 0; i < users.length; i++)
				{
					users[i]++;
				}
			}
		}
		
		// Failure rate
		ArrayList<Double[]> failRate = new ArrayList<>();
		
		// Assign index and value to the failure rate
		for (int i = 0; i < N; i++)
		{
			// If there are no attempters or failures, this divides by 0, so NaN handling is needed
			double rate = Double.isNaN((double) fails[i] / users[i]) ? 0 : (double) fails[i] / users[i];
			
			failRate.add(new Double[] { (double) i + 1, rate });
		}
		
		// Sort
		failRate.sort((o1, o2) -> Double.compare(o2[1], o1[1]));
		
		return failRate.stream().mapToInt(value -> value[0].intValue()).toArray();
	}
}