Given a number represented in the form of an array such that each element of the array stores a single digit of the number. That is, array for the number 1234 will be arr[] = {1,2,3,4}. The task is to find the least number greater than the given number but having the sum of digits equal to the given number. For simplicity: Consider the length of number can be 20 at maximum. Examples:
Input : arr[] = {0, 0, 0, 0, 0, 0, 0, 3, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 8 }; Output : 00000004799999999999 Explanation : Sum of digits = 110 Input : arr[] = {0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0}; Output : 00000003970029896089 Explanation : Sum of digits = 70
A Brute Force Approach is to:
- Start from that number and increment the number by one.
- Check the sum. If the sum is same the return the number.
- Else return to step one.
A Better Approach is to jump to the next number in O(n) time complexity, where n is the length of string.
We divide the number into 4 regions : 1st: Trailing zeros . 2nd: The lowest digit not in Region 1. 3rd: Consecutive 9s starting with the digit above Region 2. 4th: All remaining digits. Then the next number is : [Region 4+1] [Region 1] [Region 2-1] [Region 3] . Example: Input Number = 548995000 Region 1 : 000 Region 2 : 5 Region 3 : 99 Region 4 : 548 Next number = 549000499
Below is the implementation of the above approach:
C++
// CPP program to find next greater number with// same sum of digits.#include <bits/stdc++.h>using namespace std;#define pb push_backvoid getnext(int arr[], int n){ // for storing 4 regions vector<int> a1, a2, a3, a4; // trailing zeros region1 int i = n - 1; // last index while (arr[i] == 0) { a1.pb(0); i--; } // lowest region(region 2) not in region 1 a2.pb(arr[i--]); // Consecutive 9's (region 3) while (arr[i] == 9) { a3.pb(9); i--; } int j = 0; while (arr[j] == 0) j++; // Starting zeros while (j <= i) // 4th region { a4.pb(arr[j]); j++; } // Calculation of result j = a4.size() - 1; a4[j]++; // Region4 + 1 a2[0]--; // Region2 -1 int l = a1.size() + a2.size() + a3.size() + a4.size(); // Calculating the result j = n-1; i = a3.size() - 1; // Copying the third region while (i >= 0) { arr[j--] = a3[i--]; } // Copying the 2nd region i = a2.size() - 1; while (i >= 0) { arr[j--] = a2[i--]; } // Copying the 1st region i = a1.size() - 1; while (i >= 0) { arr[j--] = a1[i--]; } // Copying the 4th region i = a4.size() - 1; while (i >= 0) { arr[j--] = a4[i--]; } while (j >= 0) arr[j--] = 0;}int main(){ int arr[] = { 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 }; int n = sizeof(arr)/sizeof(arr[0]); getnext(arr, n); // Calling the function for (int i = 0; i < n; i++) cout << arr[i]; return 0;} |
Java
// Java program to find next greater number with// same sum of digits.import java.util.*;class GFG{static void getnext(int []arr, int n){ // for storing 4 regions ArrayList<Integer> a1 = new ArrayList<Integer>(); ArrayList<Integer> a2 = new ArrayList<Integer>(); ArrayList<Integer> a3 = new ArrayList<Integer>(); ArrayList<Integer> a4 = new ArrayList<Integer>(); // trailing zeros region1 int i = n - 1; // last index while (arr[i] == 0) { a1.add(0); i--; } // lowest region(region 2) not in region 1 a2.add(arr[i--]); // Consecutive 9's (region 3) while (arr[i] == 9) { a3.add(9); i--; } int j = 0; while (arr[j] == 0) j++; // Starting zeros while (j <= i) // 4th region { a4.add(arr[j]); j++; } // Calculation of result j = a4.size() - 1; a4.set(j,a4.get(j) + 1); // Region4 + 1 a2.set(0,a2.get(0) - 1); // Region2 -1 //int l = a1.size() + a2.size() + a3.size() + a4.size(); // Calculating the result j = n - 1; i = a3.size() - 1; // Copying the third region while (i >= 0) { arr[j--] = (int)a3.get(i); i--; } // Copying the 2nd region i = a2.size() - 1; while (i >= 0) { arr[j--] = (int)a2.get(i); i--; } // Copying the 1st region i = a1.size() - 1; while (i >= 0) { arr[j--] = a1.get(i); i--; } // Copying the 4th region i = a4.size() - 1; while (i >= 0) { arr[j--] = a4.get(i); i--; } while (j >= 0) arr[j--] = 0;}// Driver codepublic static void main (String[] args) { int []arr = { 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 }; int n = arr.length; getnext(arr, n); // Calling the function for (int i = 0; i < n; i++) System.out.print(arr[i]);}}// This code is contributed by mits |
Python3
# Python3 program to find next greater number with# same sum of digits.def getnext(arr, n): # for storing 4 regions a1=[]; a2=[]; a3=[]; a4=[]; # trailing zeros region1 i = n - 1; # last index while (arr[i] == 0): a1.append(0); i-=1; # lowest region(region 2) not in region 1 a2.append(arr[i]); i-=1; # Consecutive 9's (region 3) while (arr[i] == 9): a3.append(9); i-=1; j = 0; while (arr[j] == 0): j+=1; # Starting zeros while (j <= i): # 4th region a4.append(arr[j]); j+=1; # Calculation of result j = len(a4) - 1; a4[j]+=1; # Region4 + 1 a2[0]-=1; # Region2 -1 l = len(a1) + len(a2) + len(a3) + len(a4); # Calculating the result j = n-1; i = len(a3) - 1; # Copying the third region while (i >= 0): arr[j] = a3[i]; j-=1; i-=1; # Copying the 2nd region i = len(a2) - 1; while (i >= 0): arr[j] = a2[i]; j-=1; i-=1; # Copying the 1st region i = len(a1) - 1; while (i >= 0): arr[j] = a1[i]; j-=1; i-=1; # Copying the 4th region i = len(a4) - 1; while (i >= 0): arr[j] = a4[i]; j-=1; i-=1; while (j >= 0): arr[j] = 0; j-=1;# Driver codearr = [ 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 ];n = len(arr);getnext(arr, n); # Calling the functionfor i in range(0,n): print(arr[i],end="");# This code is contributed by mits |
C#
// C# program to find next greater number with// same sum of digits.using System;using System.Collections;class GFG{static void getnext(int []arr, int n){ // for storing 4 regions ArrayList a1 = new ArrayList(); ArrayList a2 = new ArrayList(); ArrayList a3 = new ArrayList(); ArrayList a4 = new ArrayList(); // trailing zeros region1 int i = n - 1; // last index while (arr[i] == 0) { a1.Add(0); i--; } // lowest region(region 2) not in region 1 a2.Add(arr[i--]); // Consecutive 9's (region 3) while (arr[i] == 9) { a3.Add(9); i--; } int j = 0; while (arr[j] == 0) j++; // Starting zeros while (j <= i) // 4th region { a4.Add(arr[j]); j++; } // Calculation of result j = a4.Count - 1; a4[j] = (int)a4[j] + 1; // Region4 + 1 a2[0] = (int)a2[0] - 1; // Region2 -1 //int l = a1.Count + a2.Count + a3.Count + a4.Count; // Calculating the result j = n - 1; i = a3.Count - 1; // Copying the third region while (i >= 0) { arr[j--] = (int)a3[i]; i--; } // Copying the 2nd region i = a2.Count - 1; while (i >= 0) { arr[j--] = (int)a2[i]; i--; } // Copying the 1st region i = a1.Count - 1; while (i >= 0) { arr[j--] = (int)a1[i]; i--; } // Copying the 4th region i = a4.Count - 1; while (i >= 0) { arr[j--] = (int)a4[i]; i--; } while (j >= 0) arr[j--] = 0;}// Driver codestatic void Main(){ int []arr = { 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 }; int n = arr.Length; getnext(arr, n); // Calling the function for (int i = 0; i < n; i++) Console.Write(arr[i]);}}// This code is contributed by mits |
PHP
<?php// PHP program to find next greater number with// same sum of digits.function getnext(&$arr, $n){ // for storing 4 regions $a1=array(); $a2=array(); $a3=array(); $a4=array(); // trailing zeros region1 $i = $n - 1; // last index while ($arr[$i] == 0) { array_push($a1,0); $i--; } // lowest region(region 2) not in region 1 array_push($a2,$arr[$i--]); // Consecutive 9's (region 3) while ($arr[$i] == 9) { array_push($a3,9); $i--; } $j = 0; while ($arr[$j] == 0) $j++; // Starting zeros while ($j <= $i) // 4th region { array_push($a4,$arr[$j]); $j++; } // Calculation of result $j = count($a4) - 1; $a4[$j]++; // Region4 + 1 $a2[0]--; // Region2 -1 $l = count($a1) + count($a2) + count($a3) + count($a4); // Calculating the result $j = $n-1; $i = count($a3) - 1; // Copying the third region while ($i >= 0) { $arr[$j--] = $a3[$i--]; } // Copying the 2nd region $i = count($a2) - 1; while ($i >= 0) { $arr[$j--] = $a2[$i--]; } // Copying the 1st region $i = count($a1) - 1; while ($i >= 0) { $arr[$j--] = $a1[$i--]; } // Copying the 4th region $i = count($a4) - 1; while ($i >= 0) { $arr[$j--] = $a4[$i--]; } while ($j >= 0) $arr[$j--] = 0;} // Driver code $arr = array( 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 ); $n = count($arr); getnext($arr, $n); // Calling the function for ($i = 0; $i < $n; $i++) echo $arr[$i];// This code is contributed by mits?> |
Javascript
<script>// JavaScript program to find next greater number with// same sum of digits.function getnext(arr, n){ // for storing 4 regions let a1 = [], a2 = [], a3 = [], a4 = []; // trailing zeros region1 let i = n - 1; // last index while (arr[i] == 0) { a1.push(0); i--; } // lowest region(region 2) not in region 1 a2.push(arr[i--]); // Consecutive 9's (region 3) while (arr[i] == 9) { a3.push(9); i--; } let j = 0; while (arr[j] == 0) j++; // Starting zeros while (j <= i) // 4th region { a4.push(arr[j]); j++; } // Calculation of result j = a4.length - 1; a4[j]++; // Region4 + 1 a2[0]--; // Region2 -1 let l = a1.length + a2.length + a3.length + a4.length; // Calculating the result j = n-1; i = a3.length - 1; // Copying the third region while (i >= 0) { arr[j--] = a3[i--]; } // Copying the 2nd region i = a2.length - 1; while (i >= 0) { arr[j--] = a2[i--]; } // Copying the 1st region i = a1.length - 1; while (i >= 0) { arr[j--] = a1[i--]; } // Copying the 4th region i = a4.length - 1; while (i >= 0) { arr[j--] = a4[i--]; } while (j >= 0) arr[j--] = 0;}// driver codelet arr = [ 0, 0, 0, 0, 0, 0, 0, 3, 9, 7, 0, 0, 2, 9, 8, 9, 5, 9, 9, 0 ];let n = arr.length;getnext(arr, n); // Calling the functionfor (let i = 0; i < n; i++) document.write(arr[i]); // code is contributed by shinjanpatra</script> |
Output:
00000003970029896089
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!
