• 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

Print Power Set of a Set

Printing each word reverse in string

Common Ancestor in a Binary Tree or Binary Search Tree

LeetCode: Container With Most Water

Subset Sum Problem Dynamic programming

Find the kth number with prime factors 3, 5 and 7

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Diagonal Traversal of Binary Tree

Mirror of Tree

Interfaces in C++ (Abstract Classes in C++)

C++ OOPs Part2

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

SAP Interview Questions

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

Binary Tree in Java

Maximum of all subarrays of size k

Walmart Labs Interview Experience

Python Dictionaries

Templates in C++

SAP Hiring Off-Campus General Aptitude

Print vertical sum of all the axis in the given binary tree

Leetcode: Merge Intervals

Python String and numbers

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

flattens 2 D linked list to a single sorted link list

Serialise Deserialise N-ary Tree

SAP Off Campus Hiring_ March 2015 Analytical Aptitude

Amazon Interview On-Campus For Internship – 1

Python List

Client Server C program

Copyright © 2025 · Genesis Framework · WordPress · Log in