• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Find next greater number with same set of digits

July 20, 2014 by Dhaval Dave

Given a number n, find the smallest number that has same set of digits as n and is greater than n. If x is the greatest possible number with its set of digits, then print “not possible”.

EXAMPLES : 
Input:  n = "218765"
Output: "251678"

Input:  n = "1234"
Output: "1243"

Input: n = "4321"
Output: "Not Possible"

Input: n = "534976"
Output: "536479"

Following are few observations about the next greater number.
1) If all digits sorted in descending order, then output is always “Not Possible”.
For example, 4321. 2) If all digits are sorted in ascending order, then we need to swap last two digits.
For example, 1234.
3) For other cases, we need to process the number from rightmost side (why? because we need to find the smallest of all greater numbers)

i) the first place where the left-digit is less-than the right-digit in last example 534976, its 4.
ii)  find the smallest digit larger than 4 to the right , its 6.
iii) place it to the left of 4
iv) sort the digits to the right of 6.

CODE

#include 
#include 
#include 
using namespace std;
 
void swap(char *a, char *b){
    char temp = *a;
    *a = *b;
    *b = temp;
}
 
void findNextNumber(char num[], int n)
{
    int i, j;
    for (i = n-1; i > 0; i--)
        if (num[i] > num[i-1])
           break;
    if (i==0)
    {
        cout << "Next number is not possible";
        return;
    }
    int x = num[i-1], smallest = i;
    for (j = i+1; j < n; j++) if (num[j] > x && num[j] < num[smallest])
            smallest = j;
 
    swap(&num[smallest], &num[i-1]);
    sort(num + i, num + n);
 
    cout << "Next number with same set of digits is " << num;
 
    return;
}
 
// Driver program to test above function
int main(){
    char digits[] = "534976";
    int len = strlen(digits);
    findNextNumber(digits, len);
    return 0;
}
Output:
Next number with same set of digits is 536479

Similar Articles

Filed Under: Amazon Interview Question, Interview Questions, problem Tagged With: algorithm, Mathematical

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Find Nearest Minimum number in left side in O(n)

Client Server C program

VMWare Openings

Skiing on Mountains Matrix

Reverse a Linked List in groups of given size

Find the number ABCD such that when multipled by 4 gives DCBA.

Python Dictionaries

Trie Dictionary

Python String and numbers

Closed Parentheses checker

Serialise Deserialise N-ary Tree

Advanced SQL Injection

Difference between a LinkedList and a Binary Search Tree BST

Find the element that appears once others appears thrice

Code Chef PRGIFT Solution

Convert Decimal to Roman numbers / Romanizer HackerEarth Code

flattens 2 D linked list to a single sorted link list

simple sql injection

C++ OOPs Part2

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

How Radix sort works

Find and print longest consecutive number sequence in a given sequence in O(n)

Binary Tree in Java

Check Binary Tree is Binary Search Tree or not

Connect n ropes with minimum cost

Spanning Tree

Level order traversal in Spiral form

Maximum sum contiguous subarray of an Array

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

Copyright © 2025 · Genesis Framework · WordPress · Log in