Given an integer val. Split the given integer in two integers val1 and val2 such that val1 + val2 = val and the difference between the digit sum of val1 and val2 is not more than 1, the task is to print val1 and val2. (If there are multiple answers, then print any)
Examples:
Input: val = 161
Output: 130 and 31
Explanation: The digit sum of 130 is = 4 and the Digit sum of 31 is = 4 so the difference between them is 0 which is not more than 1.Input: val = 19
Output: 14 and 5
Naive Approach:
The naive approach is to check all the possible values by traversing.
Steps:
Steps involved in the implementation of the code:
- First we create a loop to traverse from 1 to val/2.
- Then we check if the current value(i)’s and the remaining value(val-i)’s digit sum satisfy the condition or not.
- If condition satisfy then we print those two values.
- Else continue the iterate until reach to the val/2.
- If none of the values’ digit sum satisfy the condition, then print splitting is not possible.
Below is the code for the implementation of the above approach:
C++
// C++ algorithm for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the// digit sum of the numberint digitSum(int n){ int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum;}// Function which will print two// integers whose sum will be equal// to the given integer and the// difference between their digit sum// is less than or equal to 1void printTwoNumbers(int val){ int num1 = 0, num2 = 0; // Traversing every digit of the given integer for (int i = 1; i <= val / 2; i++) { if (abs(digitSum(i) - digitSum(val - i)) <= 1) { num1 = i; num2 = val - i; break; } } // If splitting is not possible if (num1 == 0) { cout << "Splitting is not possible" << endl; return; } // Printing both of the numbers cout << "First Number: " << num1 << endl << "Second Number: " << num2 << endl;}// Driver Codeint main(){ int val = 19; printTwoNumbers(val); return 0;}// This code is contributed by Susobhan Akhuli |
Java
// Java code for the above approachimport java.util.*;class Main { // Function to calculate the // digit sum of the number public static int digitSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // Function which will print two // integers whose sum will be equal // to the given integer and the // difference between their digit sum // is less than or equal to 1 public static void printTwoNumbers(int val) { int num1 = 0, num2 = 0; // Traversing every digit of the given integer for (int i = 1; i <= val / 2; i++) { if (Math.abs(digitSum(i) - digitSum(val - i)) <= 1) { num1 = i; num2 = val - i; break; } } // If splitting is not possible if (num1 == 0) { System.out.println("Splitting is not possible"); return; } // Printing both of the numbers System.out.println("First Number: " + num1); System.out.println("Second Number: " + num2); } // Driver Code public static void main(String[] args) { int val = 19; printTwoNumbers(val); }}// This code is contributed by Vaibhav Nandan |
Python3
def digitSum(n): # Function to calculate the # digit sum of the number sum = 0 while n != 0: sum = sum + n % 10 n = n // 10 return sum# Function which will print two integers# whose sum will be equal to the given# integer and the difference between# their digit sum is <= 1def printTwoNumbers(val): num1, num2 = 0, 0 # Traversing every digit of integer for i in range(1, (val // 2) + 1): if abs(digitSum(i) - digitSum(val - i)) <= 1: num1 = i num2 = val - i break # If splitting is not possible if num1 == 0: print("Splitting is not possible") return # Printing both of the numbers print("First Number:", num1) print("Second Number:", num2)val = 19printTwoNumbers(val) |
C#
// C# algorithm for the above approachusing System;public class GFG { // Function to calculate the // digit sum of the number static int DigitSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // Function which will print two // integers whose sum will be equal // to the given integer and the // difference between their digit sum // is less than or equal to 1 static void PrintTwoNumbers(int val) { int num1 = 0, num2 = 0; // Traversing every digit of the given integer for (int i = 1; i <= val / 2; i++) { if (Math.Abs(DigitSum(i) - DigitSum(val - i)) <= 1) { num1 = i; num2 = val - i; break; } } // If splitting is not possible if (num1 == 0) { Console.WriteLine("Splitting is not possible"); return; } // Printing both of the numbers Console.WriteLine("First Number: " + num1); Console.WriteLine("Second Number: " + num2); } // Driver Code static public void Main() { int val = 19; PrintTwoNumbers(val); }} |
Javascript
// JavaScript algorithm for the above approach// Function to calculate the // digit sum of the numberfunction digitSum(n) { let sum = 0; while (n !== 0) { sum += n % 10; n = Math.floor(n / 10); } return sum;}// Function which will print two // integers whose sum will be equal// to the given integer and the // difference between their digit sum// is less than or equal to 1function printTwoNumbers(val) { let num1 = 0, num2 = 0; // Traversing every digit of the given integer for (let i = 1; i <= Math.floor(val / 2); i++) { if (Math.abs(digitSum(i) - digitSum(val - i)) <= 1) { num1 = i; num2 = val - i; break; } } // If splitting is not possible if (num1 === 0) { console.log("Splitting is not possible"); return; } // Printing both of the numbers console.log("First Number:", num1); console.log("Second Number:", num2);}// Driver Codelet val = 19;printTwoNumbers(val); |
Output
First Number: 5 Second Number: 14
Time Complexity: O(val*log(val))
Auxiliary Space: O(1)
Efficient Approach:
This can be solved with the following idea:
If you observe carefully, you’ll realize that we can solve the problem by dividing every digit of the given number equally into two numbers, in this way the difference between the digit sum of those two numbers will always remain less than or equal to 1.
Steps involved in the implementation of the code:
- We will traverse every digit of the given integer from backward. (Example: if val = 19, then we will apply the operation on 9 first then next to 1, and so on while val is greater than zero.)
- Now, if the digit from the val is odd then it can’t be divided into two equal halves, so we will give the larger part to the number whose digit sum is greater or if the digit sum is equal then we will give the larger part to any number.
- Else if the digit from the val is even then we will divide the two equal halves into both numbers.
- Finally, print both numbers.
Below is the code for the implementation of the above approach:
C++14
// C++ algorithm for the above approach#include <bits/stdc++.h>using namespace std;// Function to calculate the// digit sum of the numberint digitSum(int n){ int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum;}// Function which will print two// integers whose sum will be equal// to the given integer and the// difference between their digit sum// is less than or equal to 1void printTwoNumbers(int val){ // Initializing two different // integers int num1 = 0; int num2 = 0; int pow = 1; // Traversing every digit of // the given integer while (val > 0) { int digit = val % 10; // If the digit is even then // we will give the two halves // to both of the numbers if (digit % 2 == 0) { num1 = (digit / 2) * pow + num1; num2 = (digit / 2) * pow + num2; } // Else if the digit is odd then // we will give the larger part // to the number whose digit // sum is less else { if (digitSum(num1) > digitSum(num2)) { num1 = (digit / 2) * pow + num1; num2 = (digit / 2 + 1) * pow + num2; } else { num2 = (digit / 2) * pow + num2; num1 = (digit / 2 + 1) * pow + num1; } } pow *= 10; val /= 10; } // Printing both of the numbers cout << "First Number: " << num1 << " and Second Number: " << num2 << endl;}// Driver Codeint main(){ int val = 161; printTwoNumbers(val); return 0;}// This code is contributed by prasad264 |
Java
// Java algorithm for the above approachimport java.util.*;class GFG { // Driver Code public static void main(String[] args) { int val = 161; printTwoNumbers(val); } // Function which will print two // integers whose sum will be equal // to the given integer and the // difference between there digit sum // is less than or equal to 1 public static void printTwoNumbers(int val) { // Initializing two different // integers int num1 = 0; int num2 = 0; int pow = 1; // Traversing every digit of // the given integer while (val > 0) { int digit = val % 10; // If the digit is even then // we will give the two halves // to both of the numbers if (digit % 2 == 0) { num1 = (digit / 2) * pow + num1; num2 = (digit / 2) * pow + num2; } // Else if the digit is odd then // we will give the larger part // to the number whose digit // sum is less else { if (digitSum(num1) > digitSum(num2)) { num1 = (digit / 2) * pow + num1; num2 = (digit / 2 + 1) * pow + num2; } else { num2 = (digit / 2) * pow + num2; num1 = (digit / 2 + 1) * pow + num1; } } pow *= 10; val /= 10; } // Printing both of the numbers System.out.println("First Number: " + num1 + " and Second Number: " + num2); } // Function to calculate the // digit sum of the number public static int digitSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; }} |
Python
# Python code for the above approach# Function to calculate the# digit sum of the numberdef digitSum(n): sum = 0 while n != 0: sum = sum + n % 10 n = n // 10 return sum# Function which will print two# integers whose sum will be equal# to the given integer and the# difference between their digit sum# is less than or equal to 1def printTwoNumbers(val): # Initializing two different # integers num1 = 0 num2 = 0 pow = 1 # Traversing every digit of # the given integer while val > 0: digit = val % 10 # If the digit is even then # we will give the two halves # to both of the numbers if digit % 2 == 0: num1 = (digit // 2) * pow + num1 num2 = (digit // 2) * pow + num2 # Else if the digit is odd then # we will give the larger part # to the number whose digit # sum is less else: if digitSum(num1) > digitSum(num2): num1 = (digit // 2) * pow + num1 num2 = (digit // 2 + 1) * pow + num2 else: num2 = (digit // 2) * pow + num2 num1 = (digit // 2 + 1) * pow + num1 pow *= 10 val //= 10 # Printing both of the numbers print("First Number:", num1, "and Second Number:", num2)# Driver Codeval = 161printTwoNumbers(val)# This code is contributed by Susobhan Akhuli |
C#
// C# code to implement the approachusing System;class Program { // Function to calculate the // digit sum of the number static int DigitSum(int n) { int sum = 0; while (n != 0) { sum = sum + n % 10; n = n / 10; } return sum; } // Function which will print two // integers whose sum will be equal // to the given integer and the // difference between their digit sum // is less than or equal to 1 static void PrintTwoNumbers(int val) { // Initializing two different // integers int num1 = 0; int num2 = 0; int pow = 1; // Traversing every digit of // the given integer while (val > 0) { int digit = val % 10; // If the digit is even then // we will give the two halves // to both of the numbers if (digit % 2 == 0) { num1 = (digit / 2) * pow + num1; num2 = (digit / 2) * pow + num2; } // Else if the digit is odd then // we will give the larger part // to the number whose digit // sum is less else { if (DigitSum(num1) > DigitSum(num2)) { num1 = (digit / 2) * pow + num1; num2 = (digit / 2 + 1) * pow + num2; } else { num2 = (digit / 2) * pow + num2; num1 = (digit / 2 + 1) * pow + num1; } } pow *= 10; val /= 10; } // Printing both of the numbers Console.WriteLine("First Number: " + num1 + " and Second Number: " + num2); } // Driver Code static void Main(string[] args) { int val = 161; PrintTwoNumbers(val); }}// This code is contributed by Prajwal Kandekar |
Javascript
// JavaScript algorithm for the above approach// Function to calculate the// digit sum of the numberfunction digitSum(n){ let sum = 0; while (n !== 0) { sum += n % 10; n = Math.floor(n / 10); } return sum;}// Function which will print two// integers whose sum will be equal// to the given integer and the// difference between their digit sum// is less than or equal to 1function printTwoNumbers(val){ // Initializing two different // integers let num1 = 0; let num2 = 0; let pow = 1; // Traversing every digit of // the given integer while (val > 0) { let digit = val % 10; // If the digit is even then // we will give the two halves // to both of the numbers if (digit % 2 === 0) { num1 = Math.floor((digit / 2)) * pow + num1; num2 = Math.floor((digit / 2)) * pow + num2; } // Else if the digit is odd then // we will give the larger part // to the number whose digit // sum is less else { if (digitSum(num1) > digitSum(num2)) { num1 = Math.floor((digit / 2)) * pow + num1; num2 = Math.floor((digit / 2) + 1) * pow + num2; } else { num2 = Math.floor((digit / 2)) * pow + num2; num1 = Math.floor((digit / 2) + 1) * pow + num1; } } pow *= 10; val = Math.floor(val / 10); } // Printing both of the numbers console.log(`First Number: ${ num1 } and Second Number: ${ num2 }`);}// Driver Codelet val = 161;// Function CallprintTwoNumbers(val); |
Output
First Number: 31 and Second Number: 130
Time Complexity: O(log(val))
Auxiliary Space: O(1) space is used.
