1
\$\begingroup\$

Write a function: class Solution { public int solution(int N); } that, given an integer N, returns the smallest integer greater than N, the sum of whose digits is twice as big as the sum of digits of N. Examples: 1. Given N = 14, the function should return 19. The sum of digits of 19 (1 +9 = 10) is twice as big as sum of digits of 14 (1 + 4 = 5). 2. Given N = 10, the function should return 11. 3. Given N = 99, the function should return 9999.

class G{

    static int getSum(int n)
    {
        int sum = 0;
        while (n != 0)
        {
            sum = sum + n % 10;
            n = n / 10;
        }
        return sum;
    }
    static void smallestNumber(int N){

        int i=getSum(N);
        int d=i*2;
        int k=N;
        while (k<100000){
            if(getSum(k)==d){
                System.out.println(k);
                return;
            }
            k++;
        }  
    }

    public static void main(String[] args)
    {
        int N = 99;
        smallestNumber(N);
    }
}
\$\endgroup\$
4
\$\begingroup\$

Here is what i can recommend on what you've written:

  • You should name your variables properly: names such as i should be only used as indexes.
  • Why do you stop at k = 100000? Why not go further? What if N is bigger than that?
  • If you plan to use a while, I would recommend creating a method returning a boolean that checks if the condition is met and only stop then.
  • A class named G could have a more explicit name.

This being said, your approach is a bit simple, and you could go for a better solution that would allow you to aim for a better solve time, and complexity.

To do so, you usually look for a pattern by going through different values or the first of the iteration. It usually involves a bit of mathematics and head scratching.

You can find a more detailed explanation here for your example.

\$\endgroup\$
2
\$\begingroup\$

Youri's answer is correct in terms of general code review.

What I want to address here is that you can rework your algorithm to skip some unnecessary steps. You're taking the brute force approach, but there's a more clever way to think about this.

I'm going to take the long way to explain this, because I think it's important for you to see how I came to this solution; rather than just seeing the end result. The purpose here is to learn how to analyze how numbers behave.

NOTE
For the entirety of this answer, I'm counting digits beginning from the right. The "first" digit is the rightmost digit (100), the "second" digit is the second-rightmost digit (101), the "third" digit is the third-rightmost digit (102), and so on.

First of all, try to think of each digit like a container that can be filled up to 9. Since you're only interested in the sum of the digits, it doesn't matter (in regards to the sum) which containers you increase.

However, you are trying increment the original number. Counting up means that you increase the rightmost number first. Therefore, when looking for your result, you increase the first digit, up to 9. Let's assume you haven't found it by now. You would then roll over to the second digit.

But when you roll over to the second digit, the first digit goes back to 0. You gain +1 from the second digit, but you lose -9 from the first digit. It makes no sense to even try and check this number, because if the previous number was not high enough, this one definitely won't be.

Even if you only brought the first digit down to an 8, you end up gaining +1 from the second digit, but you still lose -1 from the first digit, which is a zero sum game.

The conclusion here is that decreasing the digits when rolling over negatively impacts the total sum of the digits, and therefore doesn't make sense. When a digit reaches 9, you can keep it at 9, and just start increasing the next digit.

Let's use 765 as an example. The target sum is (7+6+5)*2 = 36. Let's start checking:

766 = 19 
767 = 20
768 = 21
769 = 22      <---------- First number reaches 9
770 = 14
771 = 15
772 = 16
773 = 17
774 = 18
775 = 19
776 = 20
777 = 21
778 = 22
779 = 23      <---------- First sum to be higher than the 22 I point out earlier

Notice how numbers 770 to 778 were irrelevant, because their sum was lower than what we had already found. There was no reason to check any of them.

You only need to check numbers with a higher sum than you already found.

Here's a list of numbers, starting from 766, which are actually a higher total sum than you've ever seen before

 766 = 19
 767 = 20
 768 = 21
 769 = 22
 779 = 23
 789 = 24
 799 = 25
 899 = 26
 999 = 27
1999 = 28
2999 = 29
3999 = 30
4999 = 31
5999 = 32
6999 = 33
7999 = 34
8999 = 35
9999 = 36      <------ FOUND IT

There are interesting things to notice about the sequence:

  1. The first digit increased up to 9 and then stayed there forever.
  2. The second digit increased up to 9 and then stayed there forever.
  3. The third digit increased up to 9 and then stayed there forever.
  4. ...

You can use this to your advantage, because now you know how you can find the next number in the sequence:

  • Find the rightmost digit that is not already 9 and increment it.
  • If all digits are 9, prepend a 1.

Or, in code (I am a C# dev, the syntax should mostly match):

private int GetNextRecordBreakingNumber(int number)
{
    // Split the number into an array of its digits
    int[] digits = number.ToString().Select(c => c - '0').ToArray();

    // Count indices from right to left
    for(int i = digits.Length - 1; i >= 0; i--)
    {
        if(digits[i] != 9)
        {
            // Increment the non-9 digit
            digits[i] = digits[i] + 1;
            
            //Put the number back together and return it
            int result = 0;
            for(int j = 0; j < digits.Length; j++)
            {
                result = result * 10 + digits[j];
            }
            return result;
        }
    }
    
    // If we get here, all digits were 9, so just add 10^X (where X = amount of digits in old number)       
    return number + (int)Math.Pow(10, digits.Length);
}

I opted for the string-based approach to separate a number into its digits, as it is much easier to read than the mathematical approach, and the performance should not form any problem, as I will discuss below the break.

This will sequentially generate the list I showed you before:

int current = 765;
    
for(int i = 0; i < 18; i++)
{
    current = GetNextRecordBreakingNumber(current);
    Console.WriteLine(current);
}

link to fiddle.


If you use this method to find the next number, instead of doing k++;, this will cost you significantly less iterations.

Your 10 => 11 and 99 => 9999 examples prove that your code will iterate at least once, and up to n orders of magnitude (where n is the number of digits of your starting value) higher than where you started. That is massive when dealing with non-trivial numbers.

Using my suggested method, you cut down the maximum iterations to n*9. (Edit: I think this is even lower, closer to n*5 on average, but I'm fuzzy on the math here)

Case in point: 99 => 9999. Your logic would perform 9900 iterations. My logic would perform 18.

\$\endgroup\$
3
  • 3
    \$\begingroup\$ Nice solution, but you can do better. The digit sum must increase by 18. The first digit is a 5, so it can increase by min(9-5,18)=4. Remaining increase is 18-4=14. Next digit is a 6 so it can increase by min(9-6,14)=3. Remaining increase is 14-3=11. Next digit is a 7, so it can increase by min(9-7,11)=2. Remaining increase is 11-2=9. Next digit is an implied 0, and can increase by min(9-0,9)=9. Remaining increase is 9-9=0, signifying we're done. Only 4 iterations were required. \$\endgroup\$
    – AJNeufeld
    Nov 30 '21 at 20:05
  • 1
    \$\begingroup\$ @AJNeufeld: Yeah I noticed that near the end as well but I just didn't have the time to rewrite it :) Well explained! \$\endgroup\$
    – Flater
    Dec 1 '21 at 8:50
  • \$\begingroup\$ Nice answer, and kudos for taking the time to explain the logic on how to figure out the algorithmic improvement. \$\endgroup\$
    – Youri
    Dec 1 '21 at 9:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.