Fair Candy Swap

Soumya Agrawal
Last Updated: May 13, 2022

Introduction

 

Candy swap is a problem of Hashing and Array where we have to find the amount of candies we need to swap between two friends to make the total amount between them the same. Concepts related to Array and Hashing should be clear in your head if you have to master Data Structures and Algorithms

 

We will see different approaches from brute force to an efficient one, which will help you build the logic more easily.

 

Without any delays, let's move to our problem statement.

 

Problem Statement

 

There are two friends Alice and Bob, and both are very fond of candies. They have a different total number of candies. You are given two integer arrays, of which one array contains the total number of candies that Alice has, and another array contains the total number of candies that Bob has. 

 

As they are best friends, they would like to exchange one candy box each so that after the exchange, they both have the same number of candies. The total number of candies a person has is the sum of candies in each box.

 

We have to return the array, where the first index of the array will contain the number of candies that Alice must exchange, and the second index of the array will include the number of candies that Bob must exchange.

 

Note:

  • There can be multiple answers; return any one of them.
  • At least one answer will be there.

 

Let me make you more precise with the help of an example.

 

Input

Alice = [1,1] , Bob = [2,2]

 

Output:

[1,2]

In this example, Alice has in total two candies(1+1=2), and Bob has in total four candies(2+2=4), which is not the same. To make the total number of candies the same, we have to swap Alice and Bob.

If we swap Alice having candy at index=0 and Bob having candy at index=0, then Alice will have three candies in total, and Bob will also have three candies in total, which is the same amount.

After swapping the arrays will become:

Alice = [2,1] , Bob = [1,2]

 

Therefore, the result array will be [1,2].

 

If the problem statement is clear, then let's move towards the approach.

 

Building of Approach

 

The building of the logic will be clear through this pictorial representation.

 

 

 A = Alice

 B = Bob

 

Therefore, our target is to find a candy pair whose difference is exactly x/2.

If B > A, logic is precisely the same.

 

Note: Please try to solve Fair Candy Swap by yourself before heading towards the solution.

Approach 1: Brute Force

 

In the brute force approach, we will be using nested loops to calculate the difference between Alice's and Bob's candies.

 

Algorithm

 

  • We will create two variables, namely Sum1 and Sum2, and initialize them with '0'.
  • These variables will store the total number of candies of Alice and Bob.
  • We will find the candy pair whose difference is exactly (Sum1 - Sum2)/2.
  • Return the candy pair.

 

Code

 

public class faircandyswap {
public int[] swap(int[] A, int[] B) {

//For storing total amount of candies Alice and Bob have
        int sum1 = 0, sum2 = 0;
        
        //calculating the total number of candies Alice has
        for (int j =0; j <A.length; j++)
            sum1 += A[j];
        
        //calculating the total number of candies Bob has
        for (int i = 0; i < B.length; i++)
            sum2 += B[i];
        // THE CORE LOGIC OF THIS ANSWER IS DUE TO THE FOLLOWING ASSUMPTION 
        //- "THERE EXISTS AT LEAST ONE ANSWER".
        int diff = (sum1 - sum2) / 2;
        //nested loops for calculating checking that the target is same as diff or not
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < B.length; j++) {
             
                if (A[i] - B[j] == diff)
                    return new int[]{A[i], B[j]};
            }
        }
        return null;
    }

}

 

Analysis of Complexity

 

Time Complexity: Finding an array containing candies that need to be swapped is O(A+B+A*B). Where A is for Alice and B is for Bob.

 

Space Complexity: The space complexity will be O(1). No extra space is needed. 

 

Approach 2: Efficient 

 

Another approach that we will see is HashSet. HashSet stores elements by using hashing. It contains unique elements only and allows null values. We are using HashSet to improve our time complexity as it stores unique box sizes.

 

Code

 

import java.util.HashSet;

public class faircandyswap {
    public int[] fairCandySwap(int[] A, int[] B) {
        int sum1 = 0;
        int sum2 = 0;
        
        HashSet<Integer> setA = new HashSet<>();
        
        // calculate the total number of candies with Alice.
        // Also, construct a set so that it will store unique box sizes
        //(as we want to figure out only ANY answer and not all possible answers)
        for(int i=0; i<A.length; i++)
        {
            sum1 += A[i];
            setA.add(A[i]);
        }
        
        // calculate the total number of candies with Bob
        for(int i=0; i< B.length; i++)
        {
            sum2 += B[i];
        }
        
        // THE CORE LOGIC OF THIS ANSWER IS DUE TO THE FOLLOWING ASSUMPTION - 
        //"THERE EXISTS AT LEAST ONE ANSWER. "
        // So, the difference between at least one element in the array should be even
        //(divisible by 2) so that we can share half of it with the person with fewer candies.
        // As we constructed the set for Alice's candy boxes, the intention is to search 
        //for the difference in that set. So, the difference should be total number of candies with 
        //Alice has a minus total number of candies that Bob has
        int diff = (sum1-sum2)/2;
        
        // loop through all the boxes that bob has
        for(int i=0; i<B.length; i++)
        {
            // For every box that bob has, check if there exists a box with Alice that can split
         //the difference with Bob(this will ensure both of them will have the same total count).
         //When found, return the same.
            if(setA.contains(B[i]+diff))
                return new int[]{B[i]+diff, B[i]};
        }
        
        return null;
    }
}

 

Analysis of Complexity

 

Time Complexity: O(A + B) where A = Alice and B = Bob.

 

Space Complexity: O(A)

 

Frequently Asked Questions

 

  1. What is HashSet?

HashSet stores unique elements by using the mechanism called Hashing. It allows storing null values in a non-synchronized manner.

 

     2. What are the other approaches to find the number of candies to be exchanged?

         The other approach to solve this problem is Binary Search. It will take O(nlogn) time 

          and O(1) space.

 

      3. Why is the time complexity of the HashSet approach O(A + B)?

            O(A): first for iterating elements of A

             O(B): second and third for iterating elements of B

 

Key Takeaways

 

In this article, we discussed the Candy Swap problem and how we can build an approach for it:

 

The first approach is the brute force which uses nested loops to find the candy pair. We have to see whether the target(A - B) is equal to (A - B)/2 or not.

The second approach uses HashSet. So that the unique size of boxes can be stored and problems can be solved efficiently.

 

To read more about the array of HashSet, you can visit these links: HashSetArrays.

You can use CodeStudio to practice various DSA questions typically asked in interviews. It will help you in mastering efficient coding techniques.

 

Keep Coding!!!

 

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think