Largest number formed by replacing k digits

  • Thread starter SlurrerOfSpeech
  • Start date
  • Tags
    Algorithm
In summary: IEnumerable<string> Numbers() { return _Digits.Where(d => d == '0' || d == '9').ToList(); } }In summary, the algorithm is not working as a whole because it is not timing out on the test cases with larger input. The problem is that each individual function is working correctly, but it is not working as a whole. The solution is to add comments to help explain what is going on.
  • #1
SlurrerOfSpeech
141
11
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:
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");  
        }
    }
}
 
Technology news on Phys.org
  • #2
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.
 
  • Like
Likes SlurrerOfSpeech
  • #3
Mark44 said:
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.

Oops. Forgot to mention that crucial detail.
 
  • #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:
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);
    }
}
 

Related to Largest number formed by replacing k digits

1. What is the largest number that can be formed by replacing k digits?

The largest number that can be formed by replacing k digits depends on the number of digits in the original number and the value of k. Generally, the larger the original number and the smaller the value of k, the larger the resulting number will be. However, there is no specific largest number as it varies depending on the given parameters.

2. How does the process of replacing k digits to form the largest number work?

The process of forming the largest number by replacing k digits involves taking the original number and identifying the k digits that need to be replaced. These digits are then replaced with the largest possible digits, while still maintaining the same overall value of the number. This is typically done by rearranging the digits in descending order.

3. Is there a limit to the number of digits that can be replaced to form the largest number?

No, there is no limit to the number of digits that can be replaced to form the largest number. As long as there are enough digits in the original number, any number of digits can be replaced to form an even larger number. However, as the number of digits replaced increases, the resulting number may become significantly larger.

4. Can the largest number formed by replacing k digits be smaller than the original number?

It is possible for the largest number formed by replacing k digits to be smaller than the original number, depending on the value of k and the digits being replaced. For example, if the original number is 12345 and k is 2, the largest number that can be formed by replacing 2 digits would be 54321, which is smaller than the original number.

5. How is the largest number formed by replacing k digits useful in real-life situations?

The concept of forming the largest number by replacing k digits can be useful in various real-life situations, such as in data analysis and optimization problems. For example, in data analysis, this concept can be used to identify the highest possible value in a set of numbers by replacing a certain number of digits. In optimization problems, it can be used to find the maximum possible value of a function by replacing a certain number of variables.

Similar threads

  • Programming and Computer Science
Replies
2
Views
843
  • Programming and Computer Science
Replies
10
Views
2K
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
  • Programming and Computer Science
Replies
9
Views
2K
  • Programming and Computer Science
Replies
8
Views
2K
  • Programming and Computer Science
Replies
2
Views
2K
  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
3
Views
932
  • Programming and Computer Science
Replies
3
Views
3K
Back
Top