Given a number N. The task is to find the maximum possible value of SumOfDigits(A) + SumOfDigits(B) such that A + B = n (0<=A, B<=n).
Examples:
Input: N = 35
Output: 17
35 = 9 + 26
SumOfDigits(26) = 8, SumOfDigits(9) = 9
So, 17 is the answer.
Input: N = 7
Output: 7
Naive Approach: The idea is to pick a number continuously from 0 to N, that will be our first number. Then another number will be the N-first number. Then find the maximum possible value of SumOfDigits(first number) + SumOfDigits(second number).
Steps:
- Initialize a variable “ans” with the value INT_MIN. It will contain the final answer
- Iterate over the range from 0 to N and perform the following steps:
- Pick a number one by one the number picked by the loop will be our first number and the second number will be the N – first number.
- Now find the sum of digits in both numbers and maximize the value in the variable ans.
- After the above steps, print the value stored in ans as the result.
Code:
C++
#include <bits/stdc++.h>
using namespace std;
int sumOfDigitsSingle( int x)
{
int ans = 0;
while (x) {
ans += x % 10;
x /= 10;
}
return ans;
}
int sumOfDigitsTwoParts( int N)
{
int ans = INT_MIN;
for ( int i = 0; i <= N; i++) {
int temp = sumOfDigitsSingle(i)
+ sumOfDigitsSingle(N - i);
ans = max(ans, temp);
}
return ans;
}
int main()
{
int N = 35;
cout << sumOfDigitsTwoParts(N);
return 0;
}
|
Java
import java.util.*;
public class GFG {
static int sumOfDigitsSingle( int x)
{
int ans = 0 ;
while (x != 0 ) {
ans += x % 10 ;
x /= 10 ;
}
return ans;
}
static int sumOfDigitsTwoParts( int N)
{
int ans = Integer.MIN_VALUE;
for ( int i = 0 ; i <= N; i++) {
int temp = sumOfDigitsSingle(i)
+ sumOfDigitsSingle(N - i);
ans = Math.max(ans, temp);
}
return ans;
}
public static void main(String[] args)
{
int N = 35 ;
System.out.println(sumOfDigitsTwoParts(N));
}
}
|
Python3
def sumOfDigitsSingle(x):
ans = 0
while x:
ans + = x % 10
x / / = 10
return ans
def sumOfDigitsTwoParts(N):
ans = float ( '-inf' )
for i in range (N + 1 ):
temp = sumOfDigitsSingle(i) + sumOfDigitsSingle(N - i)
ans = max (ans, temp)
return ans
N = 35
print (sumOfDigitsTwoParts(N))
|
Javascript
function sumOfDigitsSingle(x)
{
let ans = 0;
while (x) {
ans += x % 10;
x = Math.floor(x / 10);
}
return ans;
}
function sumOfDigitsTwoParts(N)
{
let ans = Number.MIN_VALUE;
for (let i = 0; i <= N; i++) {
let temp = sumOfDigitsSingle(i)
+ sumOfDigitsSingle(N - i);
ans = Math.max(ans, temp);
}
return ans;
}
let N = 35;
console.log(sumOfDigitsTwoParts(N));
|
Time Complexity: O(N), because of the loop from 0 to N
Auxiliary Space: O(1), because no extra space has been used
Approach: The idea is to divide the number into two parts A and B such that A is in terms of 9 i.e. closest number to N and B = N-A. For example, N = 35, the Smallest Number that is closest to 35 is 29.
- Define a function sumOfDigitsSingle that takes an integer x as input and returns the sum of its digits.
- Define a function closest that takes an integer x as input and returns the closest number to x in terms of 9’s. This is done by iteratively multiplying ans by 10 and adding 9 until ans * 10 + 9 is greater than x.
- Define a function sumOfDigitsTwoParts that takes an integer N as input and calculates the sum of the digits of N by splitting it into two parts – the first part is the closest number to N in terms of 9’s, obtained using the closest function, and the second part is the remaining digits. The sum of the digits of these two parts is calculated using the sumOfDigitsSingle function and added together to get the final result.
- In the main function, define an integer N and call the sumOfDigitsTwoParts function with N as input.
- Print the output.
C++
#include <bits/stdc++.h>
using namespace std;
int sumOfDigitsSingle( int x)
{
int ans = 0;
while (x) {
ans += x % 10;
x /= 10;
}
return ans;
}
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);
}
int main()
{
int N = 35;
cout << sumOfDigitsTwoParts(N);
return 0;
}
|
C
#include <stdio.h>
int sumOfDigitsSingle( int x)
{
int ans = 0;
while (x) {
ans += x % 10;
x /= 10;
}
return ans;
}
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);
}
int main()
{
int N = 35;
printf ( "%d" ,sumOfDigitsTwoParts(N));
return 0;
}
|
Java
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;
}
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);
}
public static void main(String args[])
{
int N = 35 ;
System.out.print(sumOfDigitsTwoParts(N));
}
}
|
Python3
def sumOfDigitsSingle(x) :
ans = 0
while x :
ans + = x % 10
x / / = 10
return ans
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)
if __name__ = = "__main__" :
N = 35
print (sumOfDigitsTwoParts(N))
|
C#
using System;
class GFG
{
static int sumOfDigitsSingle( int x)
{
int ans = 0;
while (x != 0)
{
ans += x % 10;
x /= 10;
}
return ans;
}
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);
}
public static void Main()
{
int N = 35;
Console.Write(sumOfDigitsTwoParts(N));
}
}
|
Javascript
<script>
function sumOfDigitsSingle(x)
{
let ans = 0;
while (x)
{
ans += x % 10;
x = Math.floor(x / 10);
}
return ans;
}
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);
}
let N = 35;
document.write(sumOfDigitsTwoParts(N));
</script>
|
PHP
<?php
function sumOfDigitsSingle( $x )
{
$ans = 0;
while ( $x )
{
$ans += $x % 10;
$x /= 10;
}
return $ans ;
}
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 );
}
$N = 35;
echo sumOfDigitsTwoParts( $N );
?>
|
Time Complexity: O(log10N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!