Given two integers N and D, the task is to find the closest number to N with the sum of digits equal to D.
Examples:
Input: N = 2022, D = 25
Output: 1996
Explanation: First smaller number than 2022 with sum of digits 25 is 1996
and first greater number than 2022 with sum of digits 25 is 2599.
But 1996 is closer to 2022.Input: N = 87220000221835856, D = 102
Output: 87219999999993000
Naive Approach:
Iterate through numbers smaller and greater than the given number and check if the sum of digits is equal to the given sum.
Follow the steps to implement the naive approach:
- Initialize num1 = num2 = N.
- Decrement num1 and increment num2 at each iteration until one of them has the sum of digits equal to D and return that number.
Below is the implementation of the naive approach:
C++
// C++ program to implement Naive Approach#include <bits/stdc++.h>using namespace std;int sum_current(ulong n){ int sum = 0; while (n > 0) { sum = sum + n % 10; n /= 10; } return sum;}ulong closest_number(ulong N, int D){ ulong n1 = N, n2 = N; while (true) { if (sum_current(n1) == D) return n1; n1--; if (sum_current(n2) == D) return n2; n2++; }}// Driver codeint main(){ ulong N = 2022; int D = 25; cout << closest_number(N, D) << endl; return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG{ // Java program to implement Naive Approach static long sum_current(long n) { long sum = 0; while (n > 0) { sum = sum + n % 10; n /= 10; } return sum; } static long closest_number(long N, int D) { long n1 = N, n2 = N; while (true) { if (sum_current(n1) == D) return n1; n1--; if (sum_current(n2) == D) return n2; n2++; } } // Driver code public static void main (String[] args) { long N = 2022; int D = 25; System.out.println(closest_number(N, D)); }}// This code is contributed by satwik4409. |
Python3
# Python code to implement the approachdef sum_current(n) : sum = 0 while (n > 0) : sum = sum + n % 10 n //= 10 return sum def closest_number(N, D) : n1 = N n2 = N while (True) : if (sum_current(n1) == D) : return n1 n1 -= 1 if (sum_current(n2) == D) : return n2 n2 += 1# Driver codeN = 2022D = 25print(closest_number(N, D))# This code is contributed by code_hunt. |
C#
// C# program to implement Naive Approachusing System;public class GFG{ static long sum_current(long n) { long sum = 0; while (n > 0) { sum = sum + n % 10; n /= 10; } return sum; } static long closest_number(long N, int D) { long n1 = N, n2 = N; while (true) { if (sum_current(n1) == D) return n1; n1--; if (sum_current(n2) == D) return n2; n2++; } } // Driver code static public void Main (){ long N = 2022; int D = 25; Console.Write(closest_number(N, D)); }}// This code is contributed by hrithikgarg03188. |
Javascript
<script>// Javascript program to implement Naive Approachfunction sum_current( n){ let sum = 0; while (n > 0) { sum = sum + n % 10; n /= 10; } return sum;}function closest_number( N, D){ let n1 = N, n2 = N; while (true) { if (sum_current(n1) == D) return n1; n1--; if (sum_current(n2) == D) return n2; n2++; }}// Driver code let N = 2022; let D = 25; document.write(closest_number(N, D)); // This code is contributed by satwik4409. </script> |
Output
1996
Time Complexity: O(d*N) where d is the number of digits
Auxiliary Space: O(1)
Efficient Approach:
Manipulate digits and generate two numbers that have sum of digits D which are closest smaller and bigger than N, and return the one which is closest to N.
Follow the steps to solve this problem efficiently:
- Calculate the current sum of digits of N and store it in a variable cur_sum.
- If D = cur_sum, return N.
- If D < cur_sum:
- Starting from the last digit, make digits of N = 0 until cur_sum – D in less than 10.
- To generate a number with the sum of digits = D and is just smaller than N, set the last digit that is not 0 to make cur_sum = D.
- To generate a number with the sum of digits = D and is just greater than N, increment the last digit that is not 0 and then:
- starting from the last digit set digits = 9 until cur_sum – D is less than 10.
- set the current digit that is not 9 to make cur_sum = D.
- Among the numbers obtained above, return the one closer to N.
- If D > cur_sum:
- To generate a number with the sum of digits = D and is just greater than N:
- starting from the last digit set digits equal to 9 until D – cur_sum is less than 10.
- set the current digit that is not set to 9 to make cur_sum = D.
- To generate a number with the sum of digits = D and is just smaller than N:
- starting from the last digit set digits equal to 9 cur_sum > D.
- decrease by 1 the last digit that is not set to 9.
- starting from last digit, set digits = 0, until cur_sum – D is less than 10.
- set the current digit to make cur_sum = D.
- Among the numbers obtained above, return the one closer to N.
- To generate a number with the sum of digits = D and is just greater than N:
Below is the implementation of the efficient approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to convert vector to integerulong toInt(const vector<int>& digits){ ulong n = 0; for (int i = digits.size() - 1; i >= 0; i--) n = n * 10 + digits[i]; return n;}// Function to find the number closest to N// with sum of digits Dulong closest_number(ulong N, int D){ vector<int> digits; ulong temp_num = N; int cur_sum = 0, temp_cur_sum, index; while (temp_num > 0) { int digit = temp_num % 10; digits.push_back(digit); cur_sum += digit; temp_num /= 10; } temp_cur_sum = cur_sum; if (D == cur_sum) return N; else if (D < cur_sum) { auto n1 = digits; for (index = 0; cur_sum - D >= n1[index]; index++) { cur_sum -= n1[index]; n1[index] = 0; } n1[index] -= (cur_sum - D); auto n2 = digits; cur_sum = temp_cur_sum; for (index = 0; cur_sum >= D; index++) { cur_sum -= n2[index]; n2[index] = 0; } if (index < n2.size()) ++n2[index]; else n2.push_back(1); ++cur_sum; for (int i = index; i < n2.size() && n2[i] > 9; i++) { n2[i] = 0; if (i == n2.size() - 1) n2.push_back(1); else ++n2[i + 1]; cur_sum -= 9; } for (index = 0; D - cur_sum + n2[index] >= 10; index++) { cur_sum += (9 - n2[index]); n2[index] = 9; } n2[index] += D - cur_sum; if (N - toInt(n1) <= toInt(n2) - N) return toInt(n1); else return toInt(n2); } else { auto n1 = digits; for (index = 0; D - cur_sum + n1[index] >= 10; index++) { if (index == n1.size()) n1.push_back(0); cur_sum += (9 - n1[index]); n1[index] = 9; } if (index == n1.size()) n1.push_back(0); n1[index] += D - cur_sum; auto n2 = digits; int cur_sum = temp_cur_sum; for (index = 0; cur_sum < D && index < n2.size(); index++) { cur_sum += (9 - n2[index]); n2[index] = 9; } --n2[index]; --cur_sum; if (cur_sum < D) n2.clear(); else { for (int i = index; i < n2.size() && n2[i] < 0; i++) { n2[i] = 9; if (i == n2.size() - 1) n2.pop_back(); else --n2[i + 1]; cur_sum += 9; } for (index = 0; cur_sum - D >= n2[index]; index++) { cur_sum -= n2[index]; n2[index] = 0; } n2[index] = 9 - (cur_sum - D); } if (n2.size() > 0 && N - toInt(n2) <= toInt(n1) - N) return toInt(n2); else return toInt(n1); }}// Driver codeint main(){ ulong N = 87220000221835856; int D = 102; // Function call cout << closest_number(N, D); return 0;} |
Java
// Java Code for above approachimport java.util.*;public class Solution { // Function to convert vector to integer static long toInt(ArrayList<Integer> digits) { long n = 0; for (int i = digits.size() - 1; i >= 0; i--) n = n * 10 + digits.get(i); return n; } // Function to find the number closest to N // with sum of digits D static long closest_number(long N, int D) { ArrayList<Integer> digits = new ArrayList<>(); long temp_num = N; int cur_sum = 0, temp_cur_sum, index; while (temp_num > 0) { int digit = (int)(temp_num % 10); digits.add(digit); cur_sum += digit; temp_num /= 10; } temp_cur_sum = cur_sum; if (D == cur_sum) return N; else if (D < cur_sum) { ArrayList<Integer> n1 = new ArrayList<>(digits); for (index = 0; cur_sum - D >= n1.get(index); index++) { cur_sum -= n1.get(index); n1.set(index, 0); } n1.set(index, n1.get(index) - (cur_sum - D)); ArrayList<Integer> n2 = new ArrayList<>(digits); cur_sum = temp_cur_sum; for (index = 0; cur_sum >= D; index++) { cur_sum -= n2.get(index); n2.set(index, 0); } if (index < n2.size()) n2.set(index, n2.get(index) + 1); else n2.add(1); ++cur_sum; for (int i = index; i < n2.size() && n2.get(i) > 9; i++) { n2.set(i, 0); if (i == n2.size() - 1) n2.add(1); else n2.set(i + 1, n2.get(i + 1) + 1); cur_sum -= 9; } for (index = 0; D - cur_sum + n2.get(index) >= 10; index++) { cur_sum += (9 - n2.get(index)); n2.set(index, 9); } n2.set(index, n2.get(index + D - cur_sum)); if (N - toInt(n1) <= toInt(n2) - N) return toInt(n1); else return toInt(n2); } else { ArrayList<Integer> n1 = new ArrayList<>(digits); for (index = 0; D - cur_sum + n1.get(index) >= 10; index++) { if (index == n1.size()) n1.add(0); cur_sum += (9 - n1.get(index)); n1.set(index, 9); } if (index == n1.size()) n1.add(0); n1.set(index, n1.get(index) + D - cur_sum); ArrayList<Integer> n2 = new ArrayList<>(digits); cur_sum = temp_cur_sum; for (index = 0; cur_sum < D && index < n2.size(); index++) { cur_sum += (9 - n2.get(index)); n2.set(index, 9); } n2.set(index, n2.get(index) - 1); --cur_sum; if (cur_sum < D) n2.clear(); else { for (int i = index; i < n2.size() && n2.get(i) < 0; i++) { n2.set(i, 9); if (i == n2.size() - 1) n2.remove(n2.size() - 1); else n2.set(i + 1, n2.get(i + 1) - 1); cur_sum += 9; } for (index = 0; cur_sum - D >= n2.get(index); index++) { cur_sum -= n2.get(index); n2.set(index, 0); } n2.set(index, 9 - (cur_sum - D)); } if (n2.size() > 0 && N - toInt(n2) <= toInt(n1) - N) return toInt(n2); else return toInt(n1); } } // Driver code public static void main(String[] args) { long N = 87220000221835856L; int D = 102; // Function call System.out.println(closest_number(N, D)); }}// This code is contributed by karandeep1234 |
Python3
# Python program for the above approach# Function to convert vector to integerdef toInt(digits): n = 0 for i in range(len(digits)-1,-1 ,-1): n = n * 10 + digits[i] return n# Function to find the number closest to N# with sum of digits Ddef closest_number(N, D): digits = [] temp_num = N cur_sum = 0 while (temp_num > 0): digit = temp_num % 10 digits.append(digit) cur_sum += digit temp_num //= 10 temp_cur_sum = cur_sum if (D == cur_sum): return N elif (D < cur_sum): n1 = digits.copy() index=0 while(cur_sum - D >= n1[index]): cur_sum -= n1[index] n1[index] = 0 index += 1 n1[index] = n1[index]- (cur_sum - D) n2 = digits cur_sum = temp_cur_sum index=0 while(cur_sum >= D): cur_sum = cur_sum - n2[index] n2[index] = 0 index = index + 1 if (index < len(n2)): n2[index] += 1 else: n2.append(1) cur_sum += 1 i=index while(i < len(n2) and n2[i] > 9): n2[i] = 0 i+=1 if (i == len(n2)- 1): n2.append(1) else: n2[i + 1] += 1 cur_sum -= 9 index=0 while(D - cur_sum + n2[index] >= 10): cur_sum += (9 - n2[index]) n2[index] = 9 index += 1 n2[index] += D - cur_sum if (N - toInt(n1) <= toInt(n2) - N): return toInt(n1) else: return toInt(n2) else: n1 = digits.copy() index = 0 while(D - cur_sum + n1[index] >= 10): if (index == len(n1)): n1.append(0) cur_sum += (9 - n1[index]) n1[index] = 9 index += 1 if (index == len(n1)): n1.append(0) n1[index] += D - cur_sum n2 = digits.copy() cur_sum = temp_cur_sum index = 0 while(cur_sum < D and index < len(n2)): cur_sum += (9 - n2[index]) n2[index] = 9 index += 1 n2[index] -= 1 cur_sum -= 1 if (cur_sum < D): n2.clear() else: i = index while(i < len(n2) and n2[i] < 0): n2[i] = 9 if (i == len(n2) - 1): n2.pop() i += 1 else: n2[i + 1] -= 1 cur_sum += 9 i += 1 index = 0 while(cur_sum - D >= n2[index]): cur_sum -= n2[index] n2[index] = 0 index += 1 n2[index] = 9 - (cur_sum - D) if (len(n2) > 0 and N - toInt(n2) <= toInt(n1) - N): return toInt(n2) else: return toInt(n1) # Driver code N = 87220000221835856D = 102# Function callprint(closest_number(N, D))# This code is contributed by Atul_kumar_shrivastava. |
C#
// C# Code for above approachusing System;using System.Collections.Generic;public class Solution { // Function to convert vector to integer static long toInt(List<int> digits) { long n = 0; for (int i = digits.Count - 1; i >= 0; i--) n = n * 10 + digits[i]; return n; } // Function to find the number closest to N // with sum of digits D static long closest_number(long N, int D) { List<int> digits = new List<int>(); long temp_num = N; int cur_sum = 0, temp_cur_sum, index; while (temp_num > 0) { int digit = (int)(temp_num % 10); digits.Add(digit); cur_sum += digit; temp_num /= 10; } temp_cur_sum = cur_sum; if (D == cur_sum) return N; else if (D < cur_sum) { List<int> n1 = new List<int>(digits); for (index = 0; cur_sum - D >= n1[index]; index++) { cur_sum -= n1[index]; n1[index] = 0; } n1[index] = n1[index] - (cur_sum - D); List<int> n2 = new List<int>(digits); cur_sum = temp_cur_sum; for (index = 0; cur_sum >= D; index++) { cur_sum -= n2[index]; n2[index] = 0; } if (index < n2.Count) n2[index] = n2[index] + 1; else n2.Add(1); ++cur_sum; for (int i = index; i < n2.Count && n2[i] > 9; i++) { n2[i] = 0; if (i == n2.Count - 1) n2.Add(1); else n2[i + 1] = n2[i + 1] + 1; cur_sum -= 9; } for (index = 0; D - cur_sum + n2[index] >= 10; index++) { cur_sum += (9 - n2[index]); n2[index] = 9; } n2[index] = n2[index + D - cur_sum]; if (N - toInt(n1) <= toInt(n2) - N) return toInt(n1); else return toInt(n2); } else { List<int> n1 = new List<int>(digits); for (index = 0; D - cur_sum + n1[index] >= 10; index++) { if (index == n1.Count) n1.Add(0); cur_sum += (9 - n1[index]); n1[index] = 9; } if (index == n1.Count) n1.Add(0); n1[index] = n1[index] + D - cur_sum; List<int> n2 = new List<int>(digits); cur_sum = temp_cur_sum; for (index = 0; cur_sum < D && index < n2.Count; index++) { cur_sum += (9 - n2[index]); n2[index] = 9; } n2[index] = n2[index] - 1; --cur_sum; if (cur_sum < D) n2.Clear(); else { for (int i = index; i < n2.Count && n2[i] < 0; i++) { n2[i] = 9; if (i == n2.Count - 1) n2.Remove(n2.Count - 1); else n2[i + 1] = n2[i + 1] - 1; cur_sum += 9; } for (index = 0; cur_sum - D >= n2[index]; index++) { cur_sum -= n2[index]; n2[index] = 0; } n2[index] = 9 - (cur_sum - D); } if (n2.Count > 0 && N - toInt(n2) <= toInt(n1) - N) return toInt(n2); else return toInt(n1); } } // Driver code public static void Main(string[] args) { long N = 87220000221835856L; int D = 102; // Function call Console.WriteLine(closest_number(N, D)); }}// This code is contributed by karandeep1234 |
Javascript
// javascript program for the above approach// Function to convert vector to integerfunction toInt(digits = []){ let n = 0; for (let i = digits.length - 1; i >= 0; i--) n = n * 10 + digits[i]; return n;}// Function to find the number closest to N// with sum of digits Dfunction closest_number(N,D){ let digits= []; let temp_num = N; let cur_sum = 0, temp_cur_sum, index; while (temp_num > 0) { let digit = temp_num % 10; digits.push((digit)); cur_sum += digit; temp_num = Math.floor(temp_num / 10); } temp_cur_sum = cur_sum; if (D == cur_sum) return N; else if (D < cur_sum) { ///////////// let n1 = digits.slice(); for (let index = 0; cur_sum - D >= n1[index]; index++) { cur_sum -= n1[index]; n1[index] = 0; } n1[index] -= (cur_sum - D); /////////// let n2 = digits.slice(); cur_sum = temp_cur_sum; for (let index = 0; cur_sum >= D; index++) { cur_sum -= n2[index]; n2[index] = 0; } if (index < n2.length) ++n2[index]; else n2.push(1); ++cur_sum; for (let i = index; i < n2.length && n2[i] > 9; i++) { n2[i] = 0; if (i == n2.length - 1) n2.push(1); else ++n2[i + 1]; cur_sum -= 9; } for (index = 0; D - cur_sum + n2[index] >= 10; index++) { cur_sum += (9 - n2[index]); n2[index] = 9; } n2[index] += D - cur_sum; if (N - toInt(n1) <= toInt(n2) - N) return toInt(n1); else return toInt(n2); } else { //////////////////// let n1 = digits.slice(); for (index = 0; D - cur_sum + n1[index] >= 10; index++) { if (index == n1.length) n1.push(0); cur_sum += (9 - n1[index]); n1[index] = 9; } if (index == n1.length) n1.push(0); n1[index] += D - cur_sum; let n2 = digits.slice(); cur_sum = temp_cur_sum; for (index = 0; cur_sum < D && index < n2.length; index++) { cur_sum += (9 - n2[index]); n2[index] = 9; } --n2[index]; --cur_sum; if (cur_sum < D) n2.clear; else { for (let i = index; i < n2.length && n2[i] < 0; i++) { n2[i] = 9; if (i == n2.length - 1) n2.pop(); else --n2[i + 1]; cur_sum += 9; } for (index = 0; cur_sum - D >= n2[index]; index++) { cur_sum -= n2[index]; n2[index] = 0; } n2[index] = 9 - (cur_sum - D); } if (n2.length > 0 && N - toInt(n2) <= toInt(n1) - N) return toInt(n2); else return toInt(n1); }} let N = 87220000221835856; let D = 102; // Function call console.log(closest_number(N, D));// This code is contributed by ksam24000. |
Output
87219999999993000
Time Complexity: O(d) where d is the number of digits
Auxiliary Space: O(d)
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!
Share your thoughts in the comments
