Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

C/++/# Largest number formed by replacing k digits

Tags:
  1. Aug 9, 2016 #1
    I'm wondering if you guys can help me figure out where I'm going wrong here. The prompt is

    Given k and an n-digit number, help Sandy determine the largest possible number she can make by changing k digits.

    Full prompt here: https://www.hackerrank.com/challenges/richie-rich

    My solution is slightly brute force, however it is working on all the test cases with smaller input and isn't timing out on the test cases with larger input (the output is incorrect or there is an unspecified runtime error). I've thoroughly unit tested each individual helper function and so I'm not sure why it isn't working as a whole. I've added comments to help describe what's going on.

    Code (Text):

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    using System.Text;
    class Solution
    {
       
        private static readonly List<char> _Digits = new List<char>() { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

        // returns true or false depending on whether s is a palindrome  
        private static bool IsPalindrome(string s)
        {
            for(int i = 0, j = s.Length - 1; i < j; ++i, --j)
                if(s[i] != s[j])
                    return false;
            return true;
        }
       
        // returns a copy of string s with the char-acter at index i replaced with c
        private static string ReplaceAt(string s, int i, char c)
        {
            if(s.Length < 1) // corner case
                return string.Empty;
            var sb = new StringBuilder(s);
            sb[i] = c;
            return sb.ToString();      
        }
       
       
        // returns all strings formed from replacing a digit of number with a different digit  
        public static IEnumerable<string> SingleDigitReplacements(string number)
        {
            for(int i = 0; i < number.Length; ++i)
                foreach(char c in _Digits.Where(d => number[i] != d))
                    yield return ReplaceAt(number,i,c);
        }
       
        // returns all strings formed from replacing k digits of number with different digits
        public static IEnumerable<string> KDigitReplacements(string number, int k)
        {
            var nums = new HashSet<string>(); // use hash set because algorithm encounters repeats
            nums.Add(number); // k = 0, replaced no digits
           
            // k times, replace every digit of the number in nums with the 9 other digits,
            // add that replacement to nums
            // e.g. "13", k = 1 ---> "13" (no digits replaced)
            //                       "03", "23", ..., "93" (1st digit replaced)
            //                       "10", "11", "12", "14", ..., "19" (2nd digit replaced)
            for(int i = 0; i < k; ++i)
            {
                // the reason I have to use an inner set is because the compiler doesn't
                // like me adding to the nums while I'm looping through it
                var inner = new HashSet<string>();
                foreach(var num in nums)
                    foreach(string replacement in SingleDigitReplacements(num))
                        inner.Add(replacement);
                foreach(string replacement in inner)
                    nums.Add(replacement);
            }
            return nums;
        }
       
        static void Main(String[] args)
        {
            string[] tokens_n = Console.ReadLine().Split(' ');
            int k = Convert.ToInt32(tokens_n[1]); // max number of replacements
            string number = Console.ReadLine(); // string representation of number
           
            var replacements = KDigitReplacements(number, k); // all replacements of k digits
            var palindromes = replacements.Where(numstr => IsPalindrome(numstr)); // filter out non-palindromes
            // find max, print to console
            try
            {
             var max = palindromes.Max(numstr => Int64.Parse(numstr));
              Console.WriteLine(max);
            }
            catch(InvalidOperationException e) // no max exists
            {
                Console.WriteLine("-1");  
            }
        }
    }
     
     
  2. jcsd
  3. Aug 9, 2016 #2

    Mark44

    Staff: Mentor

    It would have been helpful to mention that the changed number has to be a palindrome. Per the examples on the page you linked to, for some numbers and some values of k, it's not possible to form a palindrome (e.g., 0011, with k = 1). In that case a value of -1 should be returned.
     
  4. Aug 9, 2016 #3
    Oops. Forgot to mention that crucial detail.
     
  5. Aug 10, 2016 #4
    Alright, I made an O(n) solution which is making the performance benchmarks and is passing 30/32 test cases! There must be some corner case I'm missing.

    Code (Text):

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    using System.Text;
    class Solution
    {  
        // returns true or false depending on whether the string underlying
        // the StringBuilder sb is a palindrome
        static bool IsPalindrome(StringBuilder sb)
        {
            for(int i = 0, j = sb.Length - 1; i < j; ++i, --j)
                if(sb[i] != sb[j])
                    return false;
            return true;
        }
       
        static string LargestPalindromeAfterKReplacements(string number, int k)
        {
            // Finds the largest palindromic number (digits are the same in reverse order)
            // that can be formed by at most k replacements of digits.
            // e.g. "001", k=2 --> "909"
            //      "001", k=1 --> "101"
            //      "001", k=0 --> "-1" (not possible)
           
            var sb = new StringBuilder(number);
         
            var replacementIndices = Enumerable.Range(0, sb.Length).ToArray();
            for(int i = 0, j = sb.Length - 1; i < j && k > 0; ++i, --j)
            {
                if(sb[i] < sb[j])
                {
                    sb[i] = sb[j];
                    replacementIndices[i] = 1;
                    k -= 1;
                }
                else if(sb[i] > sb[j])
                {
                    sb[j] = sb[i];
                    replacementIndices[i] = 1;
                    k -= 1;
                }
            }
           
            if(!IsPalindrome(sb))
                return "-1";
           
            for(int i = 0, j = sb.Length - 1; i <= j && k > 0; ++i, --j)
            {
                if(sb[i] != '9')
                {
                    if(replacementIndices[i] == 1) // if made a replacement at index i
                    {
                        sb[i] = '9';
                        sb[j] = '9';
                        k -= 1;
                    }
                    else if(k > 1) // didn't make a replacement at index i, and k > 1
                    {
                        sb[i] = '9';
                        sb[j] = '9';
                        k -= 2;                    
                    }
                    else if(i == j) // didn't make a replacement at index i, and our pointers met
                    {
                        sb[i] = '9';
                    }
                }
            }
            // In case we ran out of replacement indices,
            return sb.ToString();
        }
       
        static void Main(String[] args)
        {
            string[] tokens_n = Console.ReadLine().Split(' ');
            int k = Convert.ToInt32(tokens_n[1]); // max number of replacements
            string number = Console.ReadLine(); // string representation of number
            string converted = LargestPalindromeAfterKReplacements(number, k);
            Console.WriteLine(converted);
        }
    }

     
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Largest number formed by replacing k digits
  1. Number of digits in n! (Replies: 8)

  2. Number of digit (Replies: 2)

  3. Largest number in f90 (Replies: 13)

Loading...