Least Greater number with same digit sum

0 0 8 minutes read

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_back
 
void 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 code
public 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 code
arr = [ 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 function
 
for 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 code
static 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 code
 
let 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 function
 
for (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 zambiatek!