Table of contents

Introduction

Problem Statement

Approach 1: Brute Force

Code

10.

11.

12.

13.

14.

15.

Analysis of Complexity

16.

Approach 2: Efficient

17.

Code

18.

Analysis of Complexity

19.

Frequently Asked Questions

20.

Key Takeaways

Last Updated: Mar 27, 2024

Fair Candy Swap

Q: What is HashSet?

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

Q: 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

Q: and O(1) space.

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

Q: O(A): first for iterating elements of A

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

Author Deleted User

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;
}

}

You can also read about the Longest Consecutive Sequence.

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

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: HashSet, Arrays.

Check out this problem - Longest Subarray With Sum K

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

Keep Coding!!!

Live masterclass

Switch from non tech to high paying data analytics profile

by Alka Pandey, Data Scientist @ Hindustan Unilever

09 Oct, 2024

01:30 PM

117+ registered

Master PowerBI using Netflix Data

by Ashwin Goyal, Product @ HRS Group, Ex - Udaan, OYO

08 Oct, 2024

01:30 PM

584+ registered

Switch from non tech to high paying data analytics profile

by Alka Pandey, Data Scientist @ Hindustan Unilever

09 Oct, 2024

01:30 PM

117+ registered

Master PowerBI using Netflix Data

by Ashwin Goyal, Product @ HRS Group, Ex - Udaan, OYO

08 Oct, 2024

01:30 PM

584+ registered

View more events