# Largest number less than N with digit sum greater than the digit sum of N

Given an integer **N**, the task is to find the greatest number less than **N** such that the sum of its digits is greater than the sum of the digits of **N**. If the condition isn’t satisfied for any number then print **-1**.**Examples:**

Input:N = 100Output:99

99 is the largest number less than 100 sum of whose digits is greater than the sum of the digits of 100Input:N = 49Output:-1

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the

Essential Maths for CP Courseat a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.

**Approach:** Start a loop from **N-1** to **1** and check whether the sum of the digits of any number is greater than the sum of the digits of **N**. The first number that satisfies the condition is the required number.

Below is the implementation of the above approach:

## C++

`// C++ implementation of the approach` `#include <iostream>` `using` `namespace` `std;` `// Function to return the sum of the digits of n` `int` `sumOfDigits(` `int` `n)` `{` ` ` `int` `res = 0;` ` ` `// Loop for each digit of the number` ` ` `while` `(n > 0) {` ` ` `res += n % 10;` ` ` `n /= 10;` ` ` `}` ` ` `return` `res;` `}` `// Function to return the greatest` `// number less than n such that` `// the sum of its digits is greater` `// than the sum of the digits of n` `int` `findNumber(` `int` `n)` `{` ` ` `// Starting from n-1` ` ` `int` `i = n - 1;` ` ` `// Check until 1` ` ` `while` `(i > 0) {` ` ` `// If i satisfies the given condition` ` ` `if` `(sumOfDigits(i) > sumOfDigits(n))` ` ` `return` `i;` ` ` `i--;` ` ` `}` ` ` `// If the condition is not satisfied` ` ` `return` `-1;` `}` `// Driver code` `int` `main()` `{` ` ` `int` `n = 824;` ` ` `cout << findNumber(n);` ` ` `return` `0;` `}` |

## Java

`//Java implementation of the approach` `import` `java.io.*;` `class` `GFG {` ` ` `// Function to return the sum of the digits of n` `static` `int` `sumOfDigits(` `int` `n)` `{` ` ` `int` `res = ` `0` `;` ` ` `// Loop for each digit of the number` ` ` `while` `(n > ` `0` `) {` ` ` `res += n % ` `10` `;` ` ` `n /= ` `10` `;` ` ` `}` ` ` `return` `res;` `}` `// Function to return the greatest` `// number less than n such that` `// the sum of its digits is greater` `// than the sum of the digits of n` `static` `int` `findNumber(` `int` `n)` `{` ` ` `// Starting from n-1` ` ` `int` `i = n - ` `1` `;` ` ` `// Check until 1` ` ` `while` `(i > ` `0` `) {` ` ` `// If i satisfies the given condition` ` ` `if` `(sumOfDigits(i) > sumOfDigits(n))` ` ` `return` `i;` ` ` `i--;` ` ` `}` ` ` `// If the condition is not satisfied` ` ` `return` `-` `1` `;` `}` `// Driver code` ` ` `public` `static` `void` `main (String[] args) {` ` ` `int` `n = ` `824` `;` ` ` `System.out.println (findNumber(n));` ` ` `}` `//This code is contributed by akt_mit ` `}` |

## Python3

`# Python3 implementation of the approach` `# Function to return the sum` `# of the digits of n` `def` `sumOfDigits(n) :` ` ` `res ` `=` `0` `;` ` ` `# Loop for each digit of the number` ` ` `while` `(n > ` `0` `) :` ` ` `res ` `+` `=` `n ` `%` `10` ` ` `n ` `/` `=` `10` ` ` `return` `res;` `# Function to return the greatest` `# number less than n such that` `# the sum of its digits is greater` `# than the sum of the digits of n` `def` `findNumber(n) :` ` ` `# Starting from n-1` ` ` `i ` `=` `n ` `-` `1` `;` ` ` `# Check until 1` ` ` `while` `(i > ` `0` `) :` ` ` `# If i satisfies the given condition` ` ` `if` `(sumOfDigits(i) > sumOfDigits(n)) :` ` ` `return` `i` ` ` ` ` `i ` `-` `=` `1` ` ` `# If the condition is not satisfied` ` ` `return` `-` `1` `;` `# Driver code` `if` `__name__ ` `=` `=` `"__main__"` `:` ` ` ` ` `n ` `=` `824` `;` ` ` `print` `(findNumber(n))` `# This code is contributed by Ryuga` |

## C#

`// C# implementation of the approach` `using` `System;` `class` `GFG` `{` `// Function to return the sum` `// of the digits of n` `static` `int` `sumOfDigits(` `int` `n)` `{` ` ` `int` `res = 0;` ` ` `// Loop for each digit of` ` ` `// the number` ` ` `while` `(n > 0)` ` ` `{` ` ` `res += n % 10;` ` ` `n /= 10;` ` ` `}` ` ` `return` `res;` `}` `// Function to return the greatest` `// number less than n such that` `// the sum of its digits is greater` `// than the sum of the digits of n` `static` `int` `findNumber(` `int` `n)` `{` ` ` `// Starting from n-1` ` ` `int` `i = n - 1;` ` ` `// Check until 1` ` ` `while` `(i > 0)` ` ` `{` ` ` `// If i satisfies the given condition` ` ` `if` `(sumOfDigits(i) > sumOfDigits(n))` ` ` `return` `i;` ` ` `i--;` ` ` `}` ` ` `// If the condition is` ` ` `// not satisfied` ` ` `return` `-1;` `}` `// Driver code` `static` `public` `void` `Main ()` `{` ` ` `int` `n = 824;` ` ` `Console.WriteLine (findNumber(n));` `}` `}` `// This code is contributed by @Tushil` |

## PHP

`<?php` `//PHP implementation of the approach` `// Function to return the sum of` `// the digits of n` `function` `sumOfDigits(` `$n` `)` `{` ` ` `$res` `= 0;` ` ` `// Loop for each digit of the number` ` ` `while` `(` `$n` `> 0)` ` ` `{` ` ` `$res` `+= ` `$n` `% 10;` ` ` `$n` `/= 10;` ` ` `}` ` ` `return` `$res` `;` `}` `// Function to return the greatest` `// number less than n such that` `// the sum of its digits is greater` `// than the sum of the digits of n` `function` `findNumber(` `$n` `)` `{` ` ` `// Starting from n-1` ` ` `$i` `= ` `$n` `- 1;` ` ` `// Check until 1` ` ` `while` `(` `$i` `> 0)` ` ` `{` ` ` `// If i satisfies the given condition` ` ` `if` `(sumOfDigits(` `$i` `) > sumOfDigits(` `$n` `))` ` ` `return` `$i` `;` ` ` `$i` `--;` ` ` `}` ` ` `// If the condition is not satisfied` ` ` `return` `-1;` `}` `// Driver code` `$n` `= 824;` `echo` `findNumber(` `$n` `);` ` ` `// This code is contributed by Mukul singh` `?>` |

## Javascript

`<script>` `// javascript implementation of the approach` ` ` `// Function to return the sum of the digits of n` ` ` `function` `sumOfDigits(n)` ` ` `{` ` ` `var` `res = 0;` ` ` `// Loop for each digit of the number` ` ` `while` `(n > 0)` ` ` `{` ` ` `res += n % 10;` ` ` `n = parseInt(n/10);` ` ` `}` ` ` `return` `res;` ` ` `}` ` ` `// Function to return the greatest` ` ` `// number less than n such that` ` ` `// the sum of its digits is greater` ` ` `// than the sum of the digits of n` ` ` `function` `findNumber(n)` ` ` `{` ` ` `// Starting from n-1` ` ` `var` `i = n - 1;` ` ` `// Check until 1` ` ` `while` `(i > 0)` ` ` `{` ` ` `// If i satisfies the given condition` ` ` `if` `(sumOfDigits(i) > sumOfDigits(n))` ` ` `return` `i;` ` ` `i--;` ` ` `}` ` ` `// If the condition is not satisfied` ` ` `return` `-1;` ` ` `}` ` ` `// Driver code` ` ` `var` `n = 824;` ` ` `document.write(findNumber(n));` `// This code is contributed by Princi Singh` `</script>` |

**Output:**

819

**Time Complexity: **O(N)

**Auxiliary Space: **O(1)