Blogs Hub

Play with Chips - Array - Easy - LeetCode - MiniTV

Play with Chips - Array - Easy - LeetCode - मिनी टीवी

There are some chips, and the i-th chip is at position chips[i].

You can perform any of the two following types of moves any number of times (possibly zero) on any chip:

Move the i-th chip by 2 units to the left or to the right with a cost of 0.

Move the i-th chip by 1 unit to the left or to the right with a cost of 1.

There can be two or more chips at the same position initially.

Return the minimum cost needed to move all the chips to the same position (any position).

 

Example 1:

Input: chips = [1,2,3]

Output: 1

Explanation: Second chip will be moved to positon 3 with cost 1. First chip will be moved to position 3 with cost 0. Total cost is 1.

 

Example 2:

Input: chips = [2,2,2,3,3]

Output: 2

Explanation: Both fourth and fifth chip will be moved to position two with cost 1. Total minimum cost will be 2.

 

Constraints:

1 <= chips.length <= 100

1 <= chips[i] <= 10^9

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class MinCostToMoveChipsSoln
    {
        public int MinCostToMoveChips(int[] chips)
        {
            var map = new Dictionary<int, int>();
            int max = 0;
            int maxKey = 0;
            int count = 0;
            int evenCount = 0;                     
            int oddCount = 0;                       

            //Build the Hashmap and calculate even and odd position count.
            for (int i = 0; i < chips.Length; i++)
            {
                if (map.ContainsKey(chips[i]))
                {
                    map[chips[i]]++;                    
                }
                else
                {
                    map.Add(chips[i], 1);
                }

                if (chips[i] % 2 == 0)
                {
                    evenCount++;
                }
                else
                {
                    oddCount++;
                }
            }

            //will make collective point based on even and odd count 
            //and then by frequency.
            if (evenCount > oddCount)
            {
                foreach (var item in map)
                {
                    if(item.Key % 2 == 0)
                    {
                        if(item.Key > max)
                        {
                            max = item.Value;
                            maxKey = item.Key;
                        }
                    }
                }
            }
            else
            {
                foreach (var item in map)
                {
                    if (item.Key % 2 != 0)
                    {
                        if (item.Key > max)
                        {
                            max = item.Value;
                            maxKey = item.Key;
                        }
                    }
                }
            }

            //find the total count required
            foreach (var item in map)
            {
                if(item.Key != maxKey)
                {
                    if(item.Key > maxKey)
                    {
                        count += item.Value * ((item.Key - maxKey) % 2);
                    }
                    else
                    {
                        count += item.Value * ((maxKey - item.Key) % 2);
                    }
                }
            }
            
            return count;
        }
    }
}

 

Time Complexity: O(n)

Space Complexity: O(n)

 

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
    [TestClass]
    public class MinCostToMoveChipsSolnTests
    {
        [TestMethod]
        public void MinCostToMoveChipsSoln_First()
        {
            var chips = new int[] { 1, 2, 3 };
            var output = 1;

            var res = new MinCostToMoveChipsSoln().MinCostToMoveChips(chips);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void MinCostToMoveChipsSoln_Second()
        {
            var chips = new int[] { 2, 2, 2, 3, 3 };
            var output = 2;

            var res = new MinCostToMoveChipsSoln().MinCostToMoveChips(chips);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void MinCostToMoveChipsSoln_Third()
        {
            var chips = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30 };
            var output = 15;

            var res = new MinCostToMoveChipsSoln().MinCostToMoveChips(chips);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void MinCostToMoveChipsSoln_Fourth()
        {
            var chips = new int[] { 1, 2, 2, 2, 2 };
            var output = 1;

            var res = new MinCostToMoveChipsSoln().MinCostToMoveChips(chips);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void MinCostToMoveChipsSoln_Fifth()
        {
            var chips = new int[] { 6, 4, 7, 8, 2, 10, 2, 7, 9, 7 };
            var output = 4;

            var res = new MinCostToMoveChipsSoln().MinCostToMoveChips(chips);

            Assert.AreEqual(output, res);
        }
    }
}