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

C/++/# Finding all Kaprekar numbers in the range [p, q]

  1. Feb 6, 2017 #1
    What am I doing wrong here? The prompt is https://www.hackerrank.com/challenges/kaprekar-numbers and my well-commented solution is

    Code (Text):

    using System;
    using System.Collections.Generic;
    using System.IO;
    using System.Linq;
    class Solution
    {
        // Returns the number represented by the digits in the array
        // within the range of indices [i, j)
        static long NumberInRange(long[] arr, long i, long j)
        {
            long result = 0;
            for(; i < j; ++i)
            {
                result *= 10;
                result += arr[i];
            }
            return result;
        }
       
        // Returns true or false depending on whether k is Kaprekar
        static bool IsKaprekar(int k)
        {
            // Must use long to hold square of ints
            long square = k * k;
           
            // Get all digits of square in an array of longs
            long[] digits = square.ToString().Select(c => (long)Char.GetNumericValue(c)).ToArray();
           
            // Edge case: If there is 1 or fewer digits, return true or false depending on whether
            // the square is equal to the original number.
            if(digits.Length < 2)
                return square == k;
           
            // Get all combinations of array divided into non-empty left and right sides.
            // Return early with true if the sum of the left and right equal k.
            for(int i = 1; i < digits.Length; ++i)
            {
                // Get number represented by digits in the range of indices [0,i)
                long left = NumberInRange(digits, 0, i);
               
                // Get number represented by digits in the range of indices [i, digits.Length)
                long right = NumberInRange(digits, i, digits.Length);
               
                // "By convention, the second part may start with the digit 0, but must be nonzero."
                // https://en.wikipedia.org/wiki/Kaprekar_number
                if(right == 0)
                    continue;
               
                // If made it here, we can do the check.
                if((right + left) == k)
                    return true;
            }
           
            // If made it here, k is not Kaprekar
            return false;
        }
       
        static void Main(String[] args)
        {
            int p = int.Parse(Console.ReadLine());
            int q = int.Parse(Console.ReadLine());
            IEnumerable<int> kaprekars = Enumerable.Range(p, q - p + 1).Where(k => IsKaprekar(k));
            Console.WriteLine(kaprekars.Any() ? string.Join(" ", kaprekars) : "INVALID RANGE");
        }
    }
     
    I am passing most of the test cases but am failing the following 3.

    (1)

    1000
    10000

    (2)

    1
    10000

    (3)

    1
    99999
     
  2. jcsd
  3. Feb 6, 2017 #2
    Ah, ok. On the [1000,10000] one the expected output is

    Code (Text):

    2223 2728 4950 5050 7272 7777 9999
     
    and my output is

    Code (Text):

    2223 2728 4879 4950 5050 5292 7272 7777 9999
     
    So my algorithm is incorrectly evaluating 4879 and 5292 as Kaprekar, for example.
     
  4. Feb 6, 2017 #3
    Wait ... what?

    48792 = 23804641 and 238 + 04641 = 4879

    Aren't I right?????
     
  5. Feb 6, 2017 #4

    wle

    User Avatar

    You seem to be trying all the possible sizes for the left and right pieces. The definition on the website says that the right piece should have the same number of digits ##d## as the number ##n## itself, and the left piece is made up of the digits left over. 4879 is a four-digit number, so that means you should take the right piece to be 4641 and the left piece as 2380.
     
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: Finding all Kaprekar numbers in the range [p, q]
Loading...