Separate the Numbers – Hackerrank Challenge – C# Solution
This is the c# solution for the Hackerrank problem – Separate the Numbers – Hackerrank Challenge – C# Solution.
Source – Ryan Fehr’s repository.
/* Problem: https://www.hackerrank.com/challenges/separate-the-numbers/problem C# Language Version: 6.0 .Net Framework Version: 4.7 Tool Version : Visual Studio Community 2017 Thoughts : - Basic strategy is to split the input string into strings of width starting from 1,2,3 and so on. For each width check if each subsequent number is a successor of the previous number. e.g. 111213 for this first we take width = 1 - Numbers thus found are 1,1,1,2,1,3. It fails at second split itself as the series should go like 1,2,3,4,.... then we take width = 2 - Numbers thus found are 11,12,13 which is a proper increasing series. We print YES 11 in this case. - Handling for conditions given in the problem statement need to be done i.e. if a part contains leading zero then we need to reject the series. Gotchas: Following things require special handling - Handling for switch over of digit width. e.g. the string 91011. You start with width 1 but you've to suddenly jumnp to 2 as 9 is largest one digit number - Int32 is not sufficient. We need to use Int64 i.e. long - Special handling for boundary case of short strings e.g. 90190290 Time Complexity: O(n) //if we do a manual calculation then for each test case the loop runs are in the order of ~ O(3n) //e.g. for n = 32 the loop runs 111 times for n = 16 the loop runs 46 times and so on. Space Complexity: O(n) we save the input string in memory to process it. */ using System; class Solution { private static void SeparateNumbers(string inputText) { var numberWidth = 1; var found = false; while (numberWidth <= inputText.Length / 2) { var textPart = inputText.Substring(0, numberWidth); if (IsFirstCharZero(textPart)) { numberWidth++; continue; } //handling for big numbers. Int64 is being used var previousNum = long.Parse(textPart); var firstNum = previousNum; var j = numberWidth; var widthChangeFactor = 0; //handling for width change over. e.g. in number 91011. the number series is 9,10,11. Width being extracted will change at 10 from 1 to 2 as 9 is largest one digit number if (IsItLargestNDigitNumber(textPart, numberWidth)) widthChangeFactor++; //special handling: step block of for loop has been left empty. It is being done inside the for loop itself as it will vary depending upon condition. for (; j < inputText.Length;) { //handling for short strings. e.g. 90190290 will break in last triplet as it consists of 901,902,90 if (j + numberWidth + widthChangeFactor > inputText.Length) break; else textPart = inputText.Substring(j, numberWidth + widthChangeFactor); if (IsFirstCharZero(textPart)) break; var currentNum = long.Parse(textPart); if (currentNum - previousNum != 1) break; if (IsItLargestNDigitNumber(textPart, numberWidth + widthChangeFactor)) { widthChangeFactor++; j += numberWidth; } else j += numberWidth + widthChangeFactor; previousNum = currentNum; } if (j >= inputText.Length) { found = true; Console.WriteLine("YES {0}", firstNum); break; } numberWidth++; } if (!found) Console.WriteLine("NO"); } static void Main(string[] args) { var queryCount = int.Parse(Console.ReadLine()); for (var i = 0; i < queryCount; i++) { var inputText = Console.ReadLine(); SeparateNumbers(inputText); } } private static bool IsFirstCharZero(string textPart) { return textPart[0] == '0' ? true : false; } private static bool IsItLargestNDigitNumber(string textPart, int numberWidth) { var isLargest = true; for (var i = 0; i < textPart.Length; i++) { if (textPart[i] != '9') { isLargest = false; break; } } return isLargest; } }