Codeforces 228A: Is Your Horseshoe on the Other Hoof? – Java Solution

Codeforeces 228A:  Is your horseshoe on the other hoof? Solution in Java (Step-by-Step Explanation)

Introduction

Code forces 228A – Is Your Horseshoe on the Other Hoof? is a simple problem that is excellent for beginners who are learning about sets, duplicate values, and Java collections.

The problem gives Valera the Horse four horseshoes. Each horseshoe has a color, represented by an integer.

Valera wants to attend a party wearing four horseshoes of different colors. However, some of the horseshoes he already owns may have the same color.

Instead of replacing all four horseshoes, Valera wants to buy the minimum number of additional horseshoes needed to make all four colors different.

The main idea is very simple:

Count how many different colors Valera already has, then subtract that number from 4.

---

Problem Statement

Valera has four horseshoes:

s1 s2 s3 s4

Each number represents the color of one horseshoe.

He needs four horseshoes with four distinct colors.

If some colors are repeated, he must purchase additional horseshoes with colors that are not already present.

We need to find the minimum number of horseshoes Valera needs to buy.

---

Understanding the Problem With Examples

Example 1

Suppose the input is:

1 7 3 9

All four colors are different:

1
7
3
9

So Valera already has four unique horseshoes.

Number of unique colors:

4

Horseshoes required:

4

Therefore:

4 - 4 = 0

Output

0

No horseshoes need to be purchased.

---

Example 2

Consider:

1 1 2 3

The colors are:

1, 1, 2, 3

There are only three distinct colors:

1
2
3

The two horseshoes with color 1 cannot both contribute different colors.

Therefore, Valera needs one additional horseshoe with a new color.

4 - 3 = 1

Output

1

---

Example 3

Consider:

5 5 5 5

All four horseshoes have the same color.

There is only one unique color:

5

Valera needs four different colors, so he must buy:

4 - 1 = 3

horseshoes.

Output

3

---

The Key Observation

The problem becomes much easier once we focus on unique colors.

Valera always needs exactly four different colors.

So:

Required horseshoes = 4

If he already has uniqueColors different colors, then the number of new horseshoes required is:

4 - uniqueColors

For example:

Horseshoe colors	Unique colors	Horseshoes to buy
1 2 3 4	4	0
1 1 2 3	3	1
1 1 2 2	2	2
1 1 1 2	2	2
5 5 5 5	1	3

This observation gives us a very short solution.

---

Why Use a Set?

A Set is a Java collection that stores unique values.

For example, if we add:

1
1
2
3

to a set, the set will contain:

1, 2, 3

The duplicate 1 is automatically ignored.

That is exactly what we need because the problem asks us to determine how many different colors Valera already has.

---

HashSet in Java

We can use Java's HashSet:

Set<Integer> colors = new HashSet<>();

Here:

• Set<Integer> means the collection stores integer values.

• HashSet<> provides the implementation.

• Duplicate values are automatically ignored.

For example:

colors.add(10);
colors.add(20);
colors.add(10);
colors.add(30);

The set contains:

10, 20, 30

Its size is:

3

Even though four values were added, only three are unique.

---

Java Solution

import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        Set<Integer> colors = new HashSet<>();

        for (int i = 0; i < 4; i++) {
            colors.add(sc.nextInt());
        }

        System.out.println(4 - colors.size());

        sc.close();
    }
}

This solution is short because HashSet automatically handles duplicate colors for us.

---

Step-by-Step Code Explanation

1. Import Scanner

import java.util.Scanner;

Scanner allows us to read input from the keyboard or the online judge.

For example:

Scanner sc = new Scanner(System.in);

creates a Scanner object connected to standard input.

We can then use:

sc.nextInt()

to read an integer.

---

2. Import Set

import java.util.Set;

Set is a Java collection interface designed to store unique values.

Since horseshoe colors can be repeated, a set is a natural choice for this problem.

---

3. Import HashSet

import java.util.HashSet;

HashSet is one implementation of the Set interface.

We create it using:

Set<Integer> colors = new HashSet<>();

Now we have an empty collection that can store the unique horseshoe colors.

---

4. Read the Four Colors

The problem always gives us exactly four horseshoe colors.

Therefore, we can use a loop:

for (int i = 0; i < 4; i++) {
    colors.add(sc.nextInt());
}

The loop runs four times.

Suppose the input is:

1 1 2 3

The loop performs approximately:

Read 1 → add 1
Read 1 → duplicate, ignored
Read 2 → add 2
Read 3 → add 3

The set finally contains:

{1, 2, 3}

Therefore:

colors.size()

returns:

3

---

5. Calculate the Number of Horseshoes to Buy

Valera needs four different colors.

The number of unique colors he already owns is:

colors.size()

Therefore:

4 - colors.size()

gives the number of additional horseshoes required.

For example:

Unique colors = 3
Required colors = 4

Horseshoes to buy = 4 - 3
                  = 1

So we print:

System.out.println(4 - colors.size());

---

Detailed Dry Run

Let's use this input:

1 2 2 3

Step 1: Create an empty set

{}

Step 2: Read 1

{1}

Step 3: Read 2

{1, 2}

Step 4: Read another 2

Because a set does not store duplicates:

{1, 2}

The size remains 2.

Step 5: Read 3

{1, 2, 3}

Now:

colors.size() = 3

Valera needs four different colors.

Therefore:

4 - 3 = 1

Final Output

1

---

Why Don't We Need to Actually Choose New Colors?

A common beginner question is:

What color should the new horseshoes have?

We don't need to know the exact colors.

The problem only asks for the number of horseshoes that must be purchased.

Since the store has horseshoes of every possible color, Valera can always choose a color that he does not already have.

Therefore, we only need to count how many colors are missing.

---

Alternative Approach Without HashSet

Because there are only four numbers, we could also solve the problem by comparing the values manually.

However, that approach would require several conditions to detect duplicates.

For example, we might check whether:

s1 == s2
s1 == s3
s1 == s4
...

This quickly becomes unnecessarily complicated.

Using a HashSet makes the solution cleaner:

Set<Integer> colors = new HashSet<>();

Then Java automatically handles duplicates.

This is a good example of choosing the right data structure for a problem.

---

Time Complexity

There are always exactly four horseshoe colors.

Each value is inserted into the HashSet.

In general, inserting an element into a HashSet takes O(1) average time.

Since we process only four values, the practical running time is constant.

Time Complexity

O(1)

Space Complexity

The set can contain at most four different colors.

Therefore:

O(1)

---

Common Beginner Mistake

One common mistake is trying to count duplicates directly.

For example, you might think:

Count how many pairs are equal.

But this can become confusing when there are three or four identical colors.

Consider:

5 5 5 5

There are many equal pairs, but the answer is simply:

3

A much easier way is to count unique values:

Unique colors = 1
Required colors = 4

Answer = 4 - 1 = 3

---

Important Concept: Set Removes Duplicates

This problem is a great introduction to one of the most useful properties of a set.

Given:

[4, 4, 7, 8]

A set produces:

{4, 7, 8}

So:

Number of elements = 4
Number of unique elements = 3

The duplicate count is therefore:

4 - 3 = 1

For this problem, that duplicate count is exactly the number of horseshoes Valera needs to replace with new colors.

---

Final Algorithm

The entire algorithm can be summarized in three steps:

1. Create a HashSet to store horseshoe colors.
2. Read the four colors and insert them into the set.
3. Print 4 - set.size().

In pseudocode:

Create an empty set

Repeat 4 times:
    Read a horseshoe color
    Add it to the set

Answer = 4 - number of unique colors

Print answer

---

Final Java Code

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        Set<Integer> colors = new HashSet<>();

        for (int i = 0; i < 4; i++) {
            colors.add(sc.nextInt());
        }

        int answer = 4 - colors.size();

        System.out.println(answer);

        sc.close();
    }
}

---

Conclusion

Codeforces 228A – Is Your Horseshoe on the Other Hoof? is a straightforward problem that teaches an important programming technique: using a set to eliminate duplicate values.

The key observation is that Valera needs exactly four different colors. By storing the four given colors in a HashSet, we can immediately determine how many unique colors he already owns.

The final formula is:

Answer = 4 - number of unique colors

This problem is especially useful for beginners because it introduces:

• Java Set

• HashSet

• Duplicate removal

• Scanner input

• Loops

• Collection size

• Basic problem-solving with data structures

Once you understand how HashSet automatically ignores duplicate values, the entire problem becomes very simple.

SEO Keywords

Codeforces 228A Java solution, Is Your Horseshoe on the Other Hoof Java, Codeforces 228A solution, Java HashSet problems, Java Set example, Codeforces beginner problems, horseshoe problem solution, Java competitive programming, HashSet duplicate removal, Codeforces Java solutions.