Running Time of Algorithms – Hackerrank Challenge – C# Solution
This is the c# solution for the Hackerrank problem – Running Time of Algorithms – Hackerrank Challenge – C# Solution.
Source – Ryan Fehr’s repository.
/* Problem: https://www.hackerrank.com/challenges/runningtime/problem C# Language Version: 7.0 .Net Framework Version: 4.7 Tool Version : Visual Studio Community 2017 Thoughts : This was same as insertion sort problem present at below url: https://www.hackerrank.com/challenges/insertionsort2/problem The only additional thing required in here was to maintain a count whenever a shifting took place. I achieved it using a counter in the nested loop. From algorithm stand-point the steps remain same as for insertion sort. Time Complexity: O(n^2) //There is a nested loop. Space Complexity: O(1) //number of dynamically allocated variables remain constant for any input. */ using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static int runningTime(int[] A) { var shiftCount = 0; var j = 0; for (var i = 1; i < A.Length; i++) { var value = A[i]; j = i - 1; while (j >= 0 && value < A[j]) { A[j + 1] = A[j]; shiftCount++; j = j - 1; } A[j + 1] = value; } return shiftCount; } static void Main(String[] args) { //no need of count of elements as we use array's length property. Console.ReadLine(); var arr_temp = Console.ReadLine().Split(' '); var arr = Array.ConvertAll(arr_temp, int.Parse); var result = runningTime(arr); Console.WriteLine(result); } }