Find Two Missing Numbers in O(n)

Given an array of n unique integers where each element in the array is in range [1, n]. The array is not necessarily sorted and has all distinct elements. The task is to find missing numbers if there is any.

Input  : {10, 5, 8, 1}
Output : 2, 3, 4, 6, 7, 9

Input : {3, 2, 4}
Output : 1 

Input : arr[] = {1, 2}
Output :

Algorithm: As array is not sorted so we first add all the items into dictionary (because reading is index based and quite fast).

Step1: Loop over the array and add all the items to our dictionary. Dictionary will have array items as KEY and if item is present in array then Value would be TRUE else FALSE.

Step2: Find the greatest item of the array.

Step3: Loop from 1 to the max item of the array

Step4. For each iteration of the loop, check whether this number is present in our Dictionary. if not present then print this number, otherwise skip.

class FindTwoMissingNumbers
    {
        static void Main(string[] args)
        {
            /// Input array
            int[] arr = { 10, 2, 8, 6, 5 };
 
            /// Temporary container. Array item will be our KEY and Value
            /// would be if TRUE that means item is not missing, FALSE 
            /// means item is missing so print this item.
            /// 
            Dictionary<int, bool> dict = new Dictionary<int, bool>();
 
            /// Add all the array items to this container. Array item 
            /// will be our KEY and value would be TRUE for all the items.
            for (int i = 0; i < arr.Length; ++i)
            {
                dict.Add(arr[i], true);
            }
 
            /// Loop from 1 to n (nth item of the array, i.e. max item of the array)
            int maxItem = arr.Max(x => x);
            for (int i = 1; i <= maxItem; ++i)
            {
                /// If a number is not present that means this is missing item
                /// so print it
                if (!dict.ContainsKey(i))
                {
                    Console.WriteLine(i);
                }
            }
 
            Console.ReadKey();
        }
    }

 

Find all symmetric pairs from a given array in C#

Input: arr[,] = {{11, 20}, {30, 40}, {5, 10}, {40, 30}, {10, 5}}
Output: (30, 40) , (5, 10)
Explanation: (a,b),(c,d) this will be symmetric is a=d and b=c.
Logic: Think of one pair as key-value pair and add them in a dictionary. 
Now loop over the array and first check whether current pair's second 
element exists in dictionary or not if not then insert this current 
pair as key-value pair. If it exists then check whether first
element of this pair equals to dictionary value. 

static void Main(string[] args)
        {
            int[,] arrInput = new int[,] { { 11, 20 }, { 30, 40 }, { 5, 10 }, { 40, 30 }, { 10, 5 } };
            Dictionary<int, int> dict = new Dictionary<int, int>();
            int key = 0, value = 0, temp = 0;
            for (int i = 0; i < arrInput.GetLength(0); ++i)
            {
                key = arrInput[i, 0];
                value = arrInput[i, 1];

                if (dict.Keys.Any(x => x == value))
                {
                    temp = dict.Keys.Where(x => x == value).Single();
                    if (key == dict[temp])
                    {
                        Console.WriteLine(string.Format("key: {0}, Value: {1}", value, key));
                    }
                    else
                    {
                        dict.Add(key, value);
                    }
                }
                else
                {
                    dict.Add(key, value);
                }
            }
            Console.ReadKey();
        }

Library Fine code in C#

Problem source: https://www.hackerrank.com/challenges/library-fine

The Head Librarian at a library wants you to make a program that calculates the fine for returning the book after the return date. You are given the actual and the expected return dates. Calculate the fine as follows:

  1. If the book is returned on or before the expected return date, no fine will be charged.
  2. If the book is returned in the same month as the expected return date, Fine = 15 Hackos × Number of late days
  3. If the book is not returned in the same month but in the same year as the expected return date, Fine = 500 Hackos × Number of late months
  4. If the book is not returned in the same year, the fine is fixed at 10000 Hackos.

Input Format

You are given the actual and the expected return dates in D M Y format respectively. There are two lines of input. The first line contains the D M Y values for the actual return date and the next line contains the D M Y values for the expected return date.

Constraints
1D31
1M12
1Y3000

Output Format

Output a single value equal to the fine.

Sample Input

9 6 2015
6 6 2015

Sample Output

45

class Library_Fine_Hackerrank
{
static void Main(string[] args)
{
int[] arrActual = Console.ReadLine().Split(‘ ‘).Select(x => Convert.ToInt32(x)).ToArray();
int[] arrExpected = Console.ReadLine().Split(‘ ‘).Select(x => Convert.ToInt32(x)).ToArray();

if (arrActual[2] > arrExpected[2])
{
Console.WriteLine(10000);
}
else if (arrActual[2] == arrExpected[2])
{
if (arrActual[1] > arrExpected[1])
{
Console.WriteLine(500 * Math.Abs(arrActual[1] – arrExpected[1]));
}
else if (arrActual[1] == arrExpected[1])
{
if (arrActual[0] <= arrExpected[0])
{
Console.WriteLine(0);
}
else
{
Console.WriteLine(15 * Math.Abs(arrActual[0] – arrExpected[0]));
}
}
else if (arrActual[1] < arrExpected[1])
{
Console.WriteLine(0);
}
}
else if (arrActual[2] < arrExpected[2])
{
Console.WriteLine(0);
}

Console.ReadKey();
}
}

Angry Professor code in C#

The professor is conducting a course on Discrete Mathematics to a class of N students. He is angry at the lack of their discipline, and he decides to cancel the class if there are fewer than K students present after the class starts.

Given the arrival time of each student, your task is to find out if the class gets cancelled or not.

Input Format

The first line of the input contains T, the number of test cases. Each test case contains two lines.
The first line of each test case contains two space-separated integers, N and K.
The next line contains N space-separated integers, a1,a2,…,aN, representing the arrival time of each student.

If the arrival time of a given student is a non-positive integer (ai≤0), then the student enters before the class starts. If the arrival time of a given student is a positive integer (ai>0), the student enters after the class has started.

Output Format

For each testcase, print “YES” (without quotes) if the class gets cancelled and “NO” (without quotes) otherwise.

Constraints

1≤T≤10
1≤N≤1000
1≤K≤N
−100≤ai≤100,where i∈[1,N]

Note
If a student enters the class exactly when it starts (ai=0), the student is considered to have entered before the class has started.

Sample Input

2
4 3
-1 -3 4 2
4 2
0 -1 2 1

Sample Output

YES
NO

 

class Angry_Professor_Hackerrank
{
static void Main(string[] args)
{
int noOfTestCases = Convert.ToInt32(Console.ReadLine());
for (int i = 0; i < noOfTestCases; ++i)
{
int minNoOfStudents = Convert.ToInt32(Console.ReadLine().Split(‘ ‘)[1]);
List arrivalTimeList = Console.ReadLine().Split(‘ ‘).Select(x => Convert.ToInt32(x)).ToList();
int noOfArrivedStudents = arrivalTimeList.Count(x => x <= 0);
if (noOfArrivedStudents >= minNoOfStudents)
{
Console.WriteLine(“NO”);
}
else
{
Console.WriteLine(“YES”);
}
}
Console.ReadKey();
}
}

Cut the sticks

Problem source: https://www.hackerrank.com/challenges/cut-the-sticks

You are given N sticks, where the length of each stick is a positive integer. A cut operation is performed on the sticks such that all of them are reduced by the length of the smallest stick.

Suppose we have six sticks of the following lengths:

5 4 4 2 2 8

Then, in one cut operation we make a cut of length 2 from each of the six sticks. For the next cut operation four sticks are left (of non-zero length), whose lengths are the following:

3 2 2 6

The above step is repeated until no sticks are left.

Given the length of N sticks, print the number of sticks that are cut in subsequent cut operations.

Note: For each cut operation, you have to recalcuate the length of smallest sticks (excluding zero-length sticks).

Input Format
The first line contains a single integer N.
The next line contains N integers: a0, a1,…aN-1 separated by space, where ai represents the length of ith stick.

Output Format
For each operation, print the number of sticks that are cut, on separate lines.

Constraints
1 ≤ N ≤ 1000
1 ≤ ai ≤ 1000

Sample Input #00

6
5 4 4 2 2 8

Sample Output #00

6
4
2
1

Sample Input #01

8
1 2 3 4 3 3 2 1

Sample Output #01

8
6
4
1

 

class Cut_The_Stick
{
static void Main(string[] args)
{
int noOfSticks = Convert.ToInt32(Console.ReadLine());
string strInput = Console.ReadLine();
List<int> list = new List<int>();
int min = 0;
list.AddRange(strInput.Split(‘ ‘).Select(x => Convert.ToInt32(x)));

while (list.Count() > 0)
{
Console.WriteLine(list.Count());
min = list.Min();
list = list.Select(x => x – min).Where(x => x > 0).ToList();
}
Console.ReadKey();
}
}

Sort Datatable using Linq C#.

Here I will show how to sort datatable using Linq C# queries.

using System;
using System.Data;
using System.Web.UI;

public partial class DataTable_Sorting : System.Web.UI.Page
{
    protected void Page_Load(object sender, EventArgs  e)
    {
        if (!Page.IsPostBack)
        {
            GetnSortDatatable(GenerateDatatable());
        }
    }

    private DataTable GenerateDatatable()
    {
        using (DataTable dtEmp = new DataTable())
        {
            dtEmp.Columns.Add(“Name”, typeof(string));
            dtEmp.Columns.Add(“Designation”, typeof(string));
            dtEmp.Columns.Add(“Salary”, typeof(decimal));
            dtEmp.Columns.Add(“Deduction”, typeof(decimal));

            string[] names = { “Sunil Kumar”, “Nisha”, “Amit Jha”, “Sunil Sharma”, “Garima singh”, “Karuna Pareek”, “Aakash”, “David”, “Maya”, “Sanjeev” };

            DataRow dr;
            for (int i = 1; i <= 10; ++i)
            {
                dr = dtEmp.NewRow();
                dr[“Name”] = names[i – 1];
                dr[“Designation”] = “Designation_” + i.ToString();
                dr[“Salary”] = (i * 1000);
                dr[“Deduction”] = (i * 100);
                dtEmp.Rows.Add(dr);
            }
            return dtEmp;
        }
    }

    private void GetnSortDatatable(DataTable dtEmp)
    {
        // Original Data
        grdOriginal.DataSource = dtEmp;
        grdOriginal.DataBind();

        // Datatable sorting
        grdSorted.DataSource = (from emp in dtEmp.AsEnumerable() orderby emp[“Name”] select emp).AsDataView().ToTable();
        grdSorted.DataBind();
    }
}

 

sort

Zip Operator in LinQ C#.

Recently I found a very beautiful feature of LinQ that is “Zip Operator”. It merges two sequences by using the specified predicate function.

using System;
using System.Linq;
using System.Web.UI;

public partial class Zip_Operator : System.Web.UI.Page
{
    protected void Page_Load(object sender, EventArgs e)
    {
        if (!Page.IsPostBack)
        {
            ZipOperator();
        }
    }

    private void ZipOperator()
    {
        string[] country = { “China”, “India”, “Japan”, “South Korea”, “France” };
        string[] capital ={ “Beijing”,
                           “New Delhi”,
                           “Tokyo”,
                           “Seoul”,
                           “Paris”
                         };
        var countryCapital = country.Zip(capital, (countries, capitals) => countries + “: ” + capitals);
        string zip = “<table><th>Country : Capital</th>”;
        foreach (var str in countryCapital)
        {
            zip += “<tr><td>” + str.ToString() + “</td></tr>”;
        }
        zip += “</table>”;       
    }
}
Output is:

Country : Capital
China: Beijing
India: New Delhi
Japan: Tokyo
South Korea: Seoul
France: Paris