Dividir un número en dos partes tal que la suma de sus dígitos sea máxima

Dado un número N. La tarea es encontrar el valor máximo posible de SumOfDigits(A) + SumOfDigits(B) tal que A + B = n (0<=A, B<=n).

Ejemplos: 

Input: N = 35
Output: 17
35 = 9 + 26
SumOfDigits(26) = 8, SumOfDigits(9) = 9
So, 17 is the answer.

Input: N = 7
Output: 7

Enfoque: La idea es dividir el número en dos partes A y B de modo que A esté en términos de 9, es decir, el número más cercano a N y B = NA. Por ejemplo, N = 35, el número más pequeño que está más cerca de 35 es 29. 

// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
 
// Returns sum of digits of x
int sumOfDigitsSingle(int x)
{
    int ans = 0;
    while (x) {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}
 
// Returns closest number to x in terms of 9's.
int closest(int x)
{
    int ans = 0;
    while (ans * 10 + 9 <= x)
        ans = ans * 10 + 9;
 
    return ans;
}
 
int sumOfDigitsTwoParts(int N)
{
    int A = closest(N);
    return sumOfDigitsSingle(A) + sumOfDigitsSingle(N - A);
}
 
// Driver code
int main()
{
    int N = 35;
    cout << sumOfDigitsTwoParts(N);
    return 0;
}

// C implementation of above approach
#include <stdio.h>
 
// Returns sum of digits of x
int sumOfDigitsSingle(int x)
{
    int ans = 0;
    while (x) {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}
 
// Returns closest number to x in terms of 9's.
int closest(int x)
{
    int ans = 0;
    while (ans * 10 + 9 <= x)
        ans = ans * 10 + 9;
 
    return ans;
}
 
int sumOfDigitsTwoParts(int N)
{
    int A = closest(N);
    return sumOfDigitsSingle(A) + sumOfDigitsSingle(N - A);
}
 
// Driver code
int main()
{
    int N = 35;
    printf("%d",sumOfDigitsTwoParts(N));
    return 0;
}
 
// This code is contributed by kothavvsaakash.

// Java implementation of above approach
// Returns sum of digits of x
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG
{
static int sumOfDigitsSingle(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}
 
// Returns closest number to x
// in terms of 9's.
static int closest(int x)
{
    int ans = 0;
    while (ans * 10 + 9 <= x)
        ans = ans * 10 + 9;
 
    return ans;
}
 
static int sumOfDigitsTwoParts(int N)
{
    int A = closest(N);
    return sumOfDigitsSingle(A) +
           sumOfDigitsSingle(N - A);
}
 
// Driver code
public static void main(String args[])
{
    int N = 35;
    System.out.print(sumOfDigitsTwoParts(N));
}
}
 
// This code is contributed by
// Subhadeep Gupta

# Python 3 implementation of above approach
 
#  Returns sum of digits of x
def sumOfDigitsSingle(x) :
    ans = 0
    while x :
        ans += x % 10
        x //= 10
 
    return ans
 
# Returns closest number to x in terms of 9's
def closest(x) :
    ans = 0
    while (ans * 10 + 9 <= x) :
        ans = ans * 10 + 9
 
    return ans
 
def sumOfDigitsTwoParts(N) :
    A = closest(N)
 
    return sumOfDigitsSingle(A) + sumOfDigitsSingle(N - A)
 
 
# Driver Code
if __name__ == "__main__" :
 
    N = 35
    print(sumOfDigitsTwoParts(N))
 
# This code is contributed by ANKITRAI1

// C# implementation of above approach
// Returns sum of digits of x
 
using System;
class GFG
{
static int sumOfDigitsSingle(int x)
{
    int ans = 0;
    while (x != 0)
    {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}
  
// Returns closest number to x
// in terms of 9's.
static int closest(int x)
{
    int ans = 0;
    while (ans * 10 + 9 <= x)
        ans = ans * 10 + 9;
  
    return ans;
}
  
static int sumOfDigitsTwoParts(int N)
{
    int A = closest(N);
    return sumOfDigitsSingle(A) +
           sumOfDigitsSingle(N - A);
}
  
// Driver code
public static void Main()
{
    int N = 35;
    Console.Write(sumOfDigitsTwoParts(N));
}
}

<?php
// PHP implementation of above approach
 
// Returns sum of digits of x
function sumOfDigitsSingle($x)
{
    $ans = 0;
    while ($x)
    {
        $ans += $x % 10;
        $x /= 10;
    }
    return $ans;
}
 
// Returns closest number
// to x in terms of 9's.
function closest($x)
{
    $ans = 0;
    while ($ans * 10 + 9 <= $x)
        $ans = $ans * 10 + 9;
 
    return $ans;
}
 
function sumOfDigitsTwoParts($N)
{
    $A = closest($N);
    return sumOfDigitsSingle($A) +
           sumOfDigitsSingle($N - $A);
}
 
// Driver code
$N = 35;
echo sumOfDigitsTwoParts($N);
 
// This code is contributed
// by inder_verma
?>

<script>
 
// JavaScript implementation of above approach
 
// Returns sum of digits of x
function sumOfDigitsSingle(x)
{
    let ans = 0;
    while (x)
    {
        ans += x % 10;
        x = Math.floor(x / 10);
    }
    return ans;
}
 
// Returns closest number to x
// in terms of 9's.
function closest(x)
{
    let ans = 0;
     
    while(ans * 10 + 9 <= x)
        ans = ans * 10 + 9;
 
    return ans;
}
 
function sumOfDigitsTwoParts(N)
{
    let A = closest(N);
    return sumOfDigitsSingle(A) +
           sumOfDigitsSingle(N - A);
}
 
// Driver code
let N = 35;
 
document.write(sumOfDigitsTwoParts(N));
 
// This code is contributed by Surbhi Tyagi.
 
</script>

17

Complejidad de tiempo: O(log ₁₀ N)
Espacio auxiliar: O(1)