Given a big positive number N. The task is divide N into two number ‘A’ and ‘B’ such that difference between them is K (1 <= K <= 10100) i.e A – B = K.
Examples:
Input : N = 10, K = 2 Output : A = 6 B = 4 Input : N = 20, K = 4 Output : A = 12 B = 8
Let the two required number be ‘A’ and ‘B’. So, we know sum of ‘A’ and ‘B’ will end upto N.
So, one equation became,
A + B = N
And also, we want the difference between ‘A’ and ‘B’ equals to ‘K’.
So, another equation becomes,
A – B = K
On adding both the equation, we get
2*A = N + K
So, A = (N + K)/2
Then we can find B by, B = (N – A)
Now, to handle the Big Integer, we have store Integers in character array and define a function to perform the operation on them.
Below is C implementation of this approach:
C++
// C++ program to Divide a Big// Number into two parts#include <bits/stdc++.h>using namespace std;#define MAX 100// Function to adds two Numbers// represented as array of character.void add(char v1[], char v2[]){ int i, d, c = 0; // length of string int l1 = strlen(v1); int l2 = strlen(v2); // initializing extra character // position to 0 for (i = l1; i < l2; i++) v1[i] = '0'; for (i = l2; i < l1; i++) v2[i] = '0'; // Adding each element of character // and storing the carry. for (i = 0; i < l1 || i < l2; i++) { d = (v1[i] - '0') + (v2[i] - '0') + c; c = d / 10; d %= 10; v1[i] = '0' + d; } // If remainder remains. while (c) { v1[i] = '0' + (c % 10); c /= 10; i++; } v1[i] = '\0'; v2[l2] = '\0';}// Function to subtracts two numbers// represented by string.void subs(char v1[], char v2[]){ int i, d, c = 0; // Finding the length of the string. int l1 = strlen(v1); int l2 = strlen(v2); // initializing extra character position to 0. for (i = l2; i < l1; i++) v2[i] = '0'; // Subtracting each element of character. for (i = 0; i < l1; i++) { d = (v1[i] - '0' - c) - (v2[i] - '0'); if (d < 0) { d += 10; c = 1; } else c = 0; v1[i] = '0' + d; } v2[l2] = '\0'; i = l1 - 1; while (i > 0 && v1[i] == '0') i--; v1[i + 1] = '\0';}// Function divides a number represented by// character array a constant.int divi(char v[], int q){ int i, l = strlen(v); int c = 0, d; // Dividing each character element by constant. for (i = l - 1; i >= 0; i--) { d = c * 10 + (v[i] - '0'); c = d % q; d /= q; v[i] = '0' + d; } i = l - 1; while (i > 0 && v[i] == '0') i--; v[i + 1] = '\0'; return c;}// Function to reverses the character array.void rev(char v[]){ int l = strlen(v); int i; char cc; // Reversing the array. for (i = 0; i < l - 1 - i; i++) { cc = v[i]; v[i] = v[l - 1 - i]; v[l - i - 1] = cc; }}// Wrapper Functionvoid divideWithDiffK(char a[], char k[]){ // Reversing the character array. rev(a); rev(k); // Adding the each element of both array // and storing the sum in array a[]. add(a, k); // Dividing the array a[] by 2. divi(a, 2); // Reversing the character array to get output. rev(a); cout <<" "<< a; // Subtracting each element of array // i.e calculating a = a - b rev(a); subs(a, k); // Reversing the character array to get output. rev(a); cout <<" "<< a;}// Driven Programint main(){ char a[MAX] = "100", k[MAX] = "20"; divideWithDiffK(a, k); return 0;}// this code is contributed by shivanisinghss2110 |
C
// C program to Divide a Big// Number into two parts#include <stdio.h>#include <string.h>#define MAX 100// Function to adds two Numbers// represented as array of character.void add(char v1[], char v2[]){ int i, d, c = 0; // length of string int l1 = strlen(v1); int l2 = strlen(v2); // initializing extra character // position to 0 for (i = l1; i < l2; i++) v1[i] = '0'; for (i = l2; i < l1; i++) v2[i] = '0'; // Adding each element of character // and storing the carry. for (i = 0; i < l1 || i < l2; i++) { d = (v1[i] - '0') + (v2[i] - '0') + c; c = d / 10; d %= 10; v1[i] = '0' + d; } // If remainder remains. while (c) { v1[i] = '0' + (c % 10); c /= 10; i++; } v1[i] = '\0'; v2[l2] = '\0';}// Function to subtracts two numbers// represented by string.void subs(char v1[], char v2[]){ int i, d, c = 0; // Finding the length of the string. int l1 = strlen(v1); int l2 = strlen(v2); // initializing extra character position to 0. for (i = l2; i < l1; i++) v2[i] = '0'; // Subtracting each element of character. for (i = 0; i < l1; i++) { d = (v1[i] - '0' - c) - (v2[i] - '0'); if (d < 0) { d += 10; c = 1; } else c = 0; v1[i] = '0' + d; } v2[l2] = '\0'; i = l1 - 1; while (i > 0 && v1[i] == '0') i--; v1[i + 1] = '\0';}// Function divides a number represented by// character array a constant.int divi(char v[], int q){ int i, l = strlen(v); int c = 0, d; // Dividing each character element by constant. for (i = l - 1; i >= 0; i--) { d = c * 10 + (v[i] - '0'); c = d % q; d /= q; v[i] = '0' + d; } i = l - 1; while (i > 0 && v[i] == '0') i--; v[i + 1] = '\0'; return c;}// Function to reverses the character array.void rev(char v[]){ int l = strlen(v); int i; char cc; // Reversing the array. for (i = 0; i < l - 1 - i; i++) { cc = v[i]; v[i] = v[l - 1 - i]; v[l - i - 1] = cc; }}// Wrapper Functionvoid divideWithDiffK(char a[], char k[]){ // Reversing the character array. rev(a); rev(k); // Adding the each element of both array // and storing the sum in array a[]. add(a, k); // Dividing the array a[] by 2. divi(a, 2); // Reversing the character array to get output. rev(a); printf("%s ", a); // Subtracting each element of array // i.e calculating a = a - b rev(a); subs(a, k); // Reversing the character array to get output. rev(a); printf("%s", a);}// Driven Programint main(){ char a[MAX] = "100", k[MAX] = "20"; divideWithDiffK(a, k); return 0;} |
Java
import java.util.Arrays;public class Main { static final int MAX = 100; // Function to adds two Numbers represented as array of // character. static void add(char[] v1, char[] v2) { int i, d, c = 0; // length of string int l1 = v1.length; int l2 = v2.length; // initializing extra character position to 0 if (l1 < l2) { v1 = Arrays.copyOf(v1, l2); for (i = l1; i < l2; i++) v1[i] = '0'; } else { v2 = Arrays.copyOf(v2, l1); for (i = l2; i < l1; i++) v2[i] = '0'; } // Adding each element of character and storing the // carry. for (i = 0; i < Math.max(l1, l2); i++) { d = (v1[i] - '0') + (v2[i] - '0') + c; c = d / 10; d %= 10; v1[i] = (char)('0' + d); } // If remainder remains. while (c != 0) { if (i >= v1.length) { v1 = Arrays.copyOf(v1, v1.length + 1); } d = (v1[i] - '0') + c; c = d / 10; d %= 10; v1[i] = (char)('0' + d); i++; } } // Function to subtracts two numbers represented by // string. static void subs(char[] v1, char[] v2) { int i, d, c = 0; // Finding the length of the string. int l1 = v1.length; int l2 = v2.length; // initializing extra character position to 0. if (l2 < l1) { v2 = Arrays.copyOf(v2, l1); for (i = l2; i < l1; i++) v2[i] = '0'; } // Subtracting each element of character. for (i = 0; i < l1; i++) { d = (v1[i] - '0' - c) - (v2[i] - '0'); if (d < 0) { d += 10; c = 1; } else c = 0; v1[i] = (char)('0' + d); } i = l1 - 1; while (i > 0 && v1[i] == '0') i--; v1 = Arrays.copyOf(v1, i + 1); } // Function divides a number represented by character // array a constant. static int divi(char[] v, int q) { int i, l = v.length; int c = 0, d; // Dividing each character element by constant. for (i = l - 1; i >= 0; i--) { d = c * 10 + (v[i] - '0'); c = d % q; d /= q; v[i] = (char)('0' + d); } i = l - 1; while (i > 0 && v[i] == '0') i--; v[i + 1] = '\0'; return c; } // Function to reverses the character array. public static void rev(char v[]) { int l = v.length; int i; char cc; // Reversing the array. for (i = 0; i < l - 1 - i; i++) { cc = v[i]; v[i] = v[l - 1 - i]; v[l - i - 1] = cc; } } // Wrapper Function static void divideWithDiffK(char a[], char k[]) { // Reversing the character array. rev(a); rev(k); // Adding the each element of both array // and storing the sum in array a[]. add(a, k); // Dividing the array a[] by 2. divi(a, 2); // Reversing the character array to get output. rev(a); System.out.print(String.valueOf(a)); // Subtracting each element of array // i.e calculating a = a - b rev(a); subs(a, k); // Reversing the character array to get output. rev(a); System.out.print(String.valueOf(a)); } // Driven Program public static void main(String[] args) { char a[] = "100".toCharArray(); char k[] = "20".toCharArray(); divideWithDiffK(a, k); }} |
Python3
# Python3 program to Divide a Big# Number into two partsMAX = 100# Function to adds two Numbers# represented as array of character.def add(v1, v2): c = 0 # length of string l1 = len(v1) l2 = len(v2) # initializing extra character # position to 0 for i in range(l1, l2): v1.append('0') for i in range(l2, l1): v2.append('0') # Adding each element of character # and storing the carry. for i in range(min(l1, l2)): d = int(v1[i]) + int(v2[i]) + c c = d // 10 d %= 10 v1[i] = str(d) # If remainder remains. while (c): v1[i] = str(c % 10) c = (c // 10) i += 1 return v1# Function to subtracts two numbers# represented by string.def subs(v1, v2): c = 0 # Finding the length of the string. l1 = len(v1) l2 = len(v2) # initializing extra character position to 0. for i in range(l2, l1): v2[i] = '0' # Subtracting each element of character. for i in range(l1): d = int(v1[i]) - c - int(v2[i]) if (d < 0): d += 10 c = 1 else: c = 0 v1[i] = str(d) i = l1 - 1 while (i > 0 and v1[i] == '0'): i -= 1 return v1# Function divides a number represented by# character array a constant.def divi(v, q): l = len(v) c = 0 # Dividing each character element by constant. for i in range(l - 1, -1, -1): d = c * 10 + int(v[i]) c = d % q d = (d // q) v[i] = str(d) i = l - 1 while (i > 0 and v[i] == '0'): i -= 1 return v# Function to reverses the character array.def rev(v): l = len(v) # Reversing the array. for i in range(1 + (l - 1) // 2): cc = v[i] v[i] = v[l - 1 - i] v[l - i - 1] = cc return v# Wrapper Functiondef divideWithDiffK(a, k): # Reversing the character array. a = rev(a) k = rev(k) # Adding the each element of both array # and storing the sum in array a[]. a = add(a, k) # Dividing the array a[] by 2. a = divi(a, 2) # Reversing the character array to get output. a = rev(a) print(int("".join(a)), end=" ") # Subtracting each element of array # i.e calculating a = a - b a = rev(a) a = subs(a, k) # Reversing the character array to get output. a = rev(a) print(int("".join(a)), end=" ")# Driven Programa = list("100")k = list("20")divideWithDiffK(a, k)# This code is contributed by phasing17 |
C#
using System;public class GFG { static readonly int MAX = 100; // Function to adds two Numbers represented as array of // character. static void Add(char[] v1, char[] v2) { int i, d, c = 0; // length of string int l1 = v1.Length; int l2 = v2.Length; // initializing extra character position to 0 if (l1 < l2) { Array.Resize(ref v1, l2); for (i = l1; i < l2; i++) v1[i] = '0'; } else { Array.Resize(ref v2, l1); for (i = l2; i < l1; i++) v2[i] = '0'; } // Adding each element of character and storing the // carry. for (i = 0; i < Math.Max(l1, l2); i++) { d = (v1[i] - '0') + (v2[i] - '0') + c; c = d / 10; d %= 10; v1[i] = (char)('0' + d); } // If remainder remains. while (c != 0) { if (i >= v1.Length) { Array.Resize(ref v1, v1.Length + 1); } d = (v1[i] - '0') + c; c = d / 10; d %= 10; v1[i] = (char)('0' + d); i++; } } // Function to subtracts two numbers represented by // string. static void Subs(char[] v1, char[] v2) { int i, d, c = 0; // Finding the length of the string. int l1 = v1.Length; int l2 = v2.Length; // initializing extra character position to 0. if (l2 < l1) { Array.Resize(ref v2, l1); for (i = l2; i < l1; i++) v2[i] = '0'; } // Subtracting each element of character. for (i = 0; i < l1; i++) { d = (v1[i] - '0' - c) - (v2[i] - '0'); if (d < 0) { d += 10; c = 1; } else c = 0; v1[i] = (char)('0' + d); } i = l1 - 1; while (i > 0 && v1[i] == '0') i--; Array.Resize(ref v1, i + 1); } // Function divides a number represented by character // array a constant. static int Divi(char[] v, int q) { int i, l = v.Length; int c = 0, d; // Dividing each character element by constant. for (i = l - 1; i >= 0; i--) { d = c * 10 + (v[i] - '0'); c = d % q; d /= q; v[i] = (char)('0' + d); } i = l - 1; while (i > 0 && v[i] == '0') i--; v[i + 1] = '\0'; return c; } // Function to reverses the character array. public static void Rev(char[] v) { int l = v.Length; int i; char cc; // Reversing the array. for (i = 0; i < l - 1 - i; i++) { cc = v[i]; v[i] = v[l - 1 - i]; v[l - i - 1] = cc; } } // Wrapper Function static void DivideWithDiffK(char[] a, char[] k) { // Reversing the character array. Rev(a); Rev(k); // Adding the each element of both array // and storing the sum in array a[]. Add(a, k); // Dividing the array a[] by 2. Divi(a, 2); // Reversing the character array to get output. Rev(a); Console.Write(new string(a) + " "); // Subtracting each element of array // i.e calculating a = a - b Rev(a); Subs(a, k); // Reversing the character array to get output. Rev(a); Console.Write(new string(a)); } // Driver code public static void Main(string[] args) { char[] a = "100".ToCharArray(); char[] k = "20".ToCharArray(); DivideWithDiffK(a, k); }} |
Javascript
// JavaScript program to Divide a Big// Number into two partslet MAX = 100;// Function to adds two Numbers// represented as array of character.function add(v1, v2){ let i, d, c = 0; // length of string let l1 = v1.length; let l2 = v2.length; // initializing extra character // position to 0 for (i = l1; i < l2; i++) v1[i] = '0'; for (i = l2; i < l1; i++) v2[i] = '0'; // Adding each element of character // and storing the carry. for (i = 0; i < l1 || i < l2; i++) { d = parseInt(v1[i] ) + parseInt(v2[i] ) + c; c = Math.floor(d / 10); d %= 10; v1[i] = d.toString(); } // If remainder remains. while (c) { v1[i] = (c % 10).toString(); c = Math.floor(c / 10); i++; } return v1;}// Function to subtracts two numbers// represented by string.function subs(v1, v2){ let i, d, c = 0; // Finding the length of the string. let l1 = v1.length; let l2 = v2.length; // initializing extra character position to 0. for (i = l2; i < l1; i++) v2[i] = '0'; // Subtracting each element of character. for (i = 0; i < l1; i++) { d = parseInt(v1[i]) - c - parseInt(v2[i]); if (d < 0) { d += 10; c = 1; } else c = 0; v1[i] = d.toString(); } i = l1 - 1; while (i > 0 && v1[i] == '0') i--; return v1;}// Function divides a number represented by// character array a constant.function divi(v, q){ let i, l = v.length; let c = 0, d; // Dividing each character element by constant. for (i = l - 1; i >= 0; i--) { d = c * 10 + parseInt(v[i]); c = d % q; d = Math.floor(d / q); v[i] = d.toString(); } i = l - 1; while (i > 0 && v[i] == '0') i--; return v; // return c;}// Function to reverses the character array.function rev(v){ let l = v.length; let i; let cc; // Reversing the array. for (i = 0; i < l - 1 - i; i++) { cc = v[i]; v[i] = v[l - 1 - i]; v[l - i - 1] = cc; } return v;}// Wrapper Functionfunction divideWithDiffK(a, k){ // Reversing the character array. a = rev(a); k = rev(k); // Adding the each element of both array // and storing the sum in array a[]. a = add(a, k); // Dividing the array a[] by 2. a = divi(a, 2); // Reversing the character array to get output. a = rev(a); process.stdout.write(" " + parseInt(a.join(""))); // Subtracting each element of array // i.e calculating a = a - b a = rev(a); a = subs(a, k); // Reversing the character array to get output. a = rev(a); process.stdout.write(" " + parseInt(a.join("")));}// Driven Programlet a = "100".split("");let k = "20".split("");divideWithDiffK(a, k);// This code is contributed by phasing17 |
Output:
60 40
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!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
