• Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard
CSEstack

What do you want to Learn Today?

  • Programming
    • Tutorial- C/C++
    • Tutorial- Django
    • Tutorial- Git
    • Tutorial- HTML & CSS
    • Tutorial- Java
    • Tutorial- MySQL
    • Tutorial- Python
    • Competitive Coding Challenges
  • CSE Subject
    • (CD) Compiler Design
    • (CN) Computer Network
    • (COA) Computer Organization & Architecture
    • (DBMS) Database Management System
    • (DS) Data Structure
    • (OS) Operating System
    • (ToA) Theory of Automata
    • (WT) Web Technology
  • Interview Questions
    • Interview Questions- Company Wise
    • Interview Questions- Coding Round
    • Interview Questions- Python
    • Interview Questions- REST API
    • Interview Questions- Web Scraping
    • Interview Questions- HR Round
    • Aptitude Preparation Guide
  • GATE 2022
  • Linux
  • Trend
    • Full Stack Development
    • Artificial Intelligence (AI)
    • BigData
    • Cloud Computing
    • Machine Learning (ML)
  • Write for Us
    • Submit Article
    • Submit Source Code or Program
    • Share Your Interview Experience
  • Tools
    • IDE
    • CV Builder
    • Other Tools …
  • Jobs

How to Find Next Greater Number with Same Set of Digits in C?

Aniruddha Chaudhari/43179/0
C / C++CodeQuiz

This is Quiz question as well as asked in many placement interviews to write code to find next greater number with the same set of digits of a given number.

Problem Statement:

You have given a number. You have to find out next greater number to given number with the same set of digits.

For Example:

Input: 102
Output: 120

Input: 523
Output: 532

Input: 405
Output: 450

It is a tricky question. Logic is all about rearranging digits in the given number and finding the next greater number.

Note: This question was asked in the on-campus Microsoft placement paper.

The Algorithm to find Find Next Greater Number with Same Set of Digits:

Step 1: Traverse the given number from the rightmost digit. Keep traversing till you get a digit which is smaller than the previously traversed digit.

Consider if the given input number is “4128765”, Here while traversing from right, stop at 2 because 2 is smaller than next digit 8. If there is no such digit, there is no greater number.

Number: 4128765

Step 2: Now consider all the digits right side of 2. Find the smallest digit among them. Here smallest digit that resides right side of 2 is 5.

Number: 4128765

Step 3: Swap the two digits found in the above two steps. (marked in block letters)

Number: 4158762

Step 4: Sort all the digits right side of 5.

Number: 4152678

So 4152678 is the next greater number of  4128765 with the same set of digits.

Special Cases to Find Next Greater Number with Same Set of Digits:

  • If your digits in the given number are sorted in descending order, there is no greater number with the same set of digits.
    Example: Suppose the given number is 7432. It is the greatest number in the set of (7, 4, 3, 2). So there is no next greater number.
  • If your digits in the given number are sorted in ascending order, you just need to swap last to digits of a given number.
    Example: Suppose the given number is 2356. Swap the last to digits, you will get next greater number as 2365.

C Program to Find the Next Greater Number with Same Set of Digits:

//C++ program to find the Next Greater Number 
//with Same Set of Digits of a Given Number
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
 
//Swap is Utility function to swap 
//two characters in the string
void swap(char *strA, char *strB)
{
  char temp = *strA;
  *strA = *strB;
  *strB = temp;
}
 
//Given a number as a char array strNumber[], 
//This function finds the next greater number.  
//It modifies the same array to store the result 
//as we are using call by reference mechanism 

void  findNextNumber(char strNumber[], int nLen)
{
  int i, j;
 
  // Step 1: Start from the right most digit 
  //and find the first digit 
  // which is smaller than the digit next to it.
  for (i = nLen-1; i > 0; i--)
   if (strNumber[i] > strNumber[i-1])
     break;
 
  //If no such digit is there, then all digits 
  //might be in descending order
  //In this case there is no greater number
  //possible with same set of digits
  if (i==0)
  {
    cout << "Next number is not possible";
    return;
  }
 
  // Step 2: Find the smallest digit on right side of (i-1)'th digit 
  // that is greater than strNumber[i-1]
  int x = strNumber[i-1], nSmallestLoc = i;
  for (j = i+1; j < nLen; j++) 
    if (strNumber[j] > x && strNumber[j] < strNumber[nSmallestLoc])
      nSmallestLoc = j;
 
  // Step 3: Swap the above found smallest digit with number[i-1]
  // using utilit function swap
  swap(&strNumber[nSmallestLoc], &strNumber[i-1]);
  // Step 4: Sort the all the digits in strNumber 
  //after (i-1) in ascending order
  sort(strNumber + i, strNumber + nLen);
  return;
}
 
// Main Driver program to test function findNextNumber()
int main()
{
  char strNumber[] = "454652";
  cout<<"Next Greater Number with Same Set of Digits";
  cout<<"\nGiven Number is "<<strNumber;
  int nLen = strlen(strNumber);
  findNextNumber(strNumber, nLen);
  cout<<"\nNext greater number is "<<strNumber;	
  return 0;
}

Output:

Next Greater Number with Same Set of Digits
Given Number is 454652
Next greater number is 455246

To solve this kind of questions, you have to be great at C/C++ programming concepts.

Complexity & Performance of Program:

You can reduce the complexity of the above program in the following ways.

  • In step two we are finding the smallest number. We can improve performance by binary searching, instead of linear search.
  • In step four, you can use the most optimized sorting technique.
  • You can also improve the performance by checking special cases before calling findNextNumber().

What other optimize solution you can program? If you can take this challenge to solve in Python or Java programmer, kindly share your code with me in the comment.

How to Improve your competitive Programming skills?

Do you want to get into one of the top product-based companies like Microsoft, Google, Facebook…?

It is the dream for many of us.

You have to build your competitive programming skills. And there is no shortcut.

Interested in building your competitive programming skills? Take these coding challenges.

Happy Programming!

coding challengecpp
Aniruddha Chaudhari
I am complete Python Nut, love Linux and vim as an editor. I hold a Master of Computer Science from NIT Trichy. I dabble in C/C++, Java too. I keep sharing my coding knowledge and my own experience on CSEstack.org portal.

Your name can also be listed here. Got a tip? Submit it here to become an CSEstack author.

Leave a Reply Cancel reply

Why?

Why Competitive Programming Important?

Coding Challenges for Practice

  1. Count Common Factor
  2. Does it Divide
  3. Sum of Sub Arrays
  4. Pair of Desired Sum
  5. Remove Duplicate Char from String
  6. Sort String by Char Freq (Python)
  7. Sort String by Char Freq (Java)
  8. Split Array into Equal Sum Subarray
  9. Validate IP Address
  10. Validate PAN Card Number
  11. Validate Sudoku
  12. Sort Circular Rotated Array
  13. Min Arrow to Burst Bubbles
  14. Min Cost to Paint All Houses [Amazon]
  15. HourGlass with Largest Sum
  16. Max Profit by Buying/Selling Stocks
  17. Hailstone Sequence
  18. Reverse String without affecting Special Characters
  19. Secure Conversation by Encry/Decry
  20. Special Elements in Matrix
  21. Next Greater No with Same set of Digits
  22. Smallest Subarray with Sum Greater than Given Number
  23. Group Anagrams
  24. Find Duplicates in Array in O(n)
  25. Find Two Unique Numbers from Array in O(n)
  26. Number Patterns & Finding Smallest Number
  27. First Unique Element in a Stream
  28. Flip Equivalent Binary Trees [TeachMint]
  29. Minimum Cost of Merging Files [Amazon]
  30. Minimum Distance for Truck to Deliver Order [Amazon]
  31. Order Task for Given Dependencies
  32. Design Music Player
  33. Multilevel Parking System Design
  34. Minimum Coins Required
  35. Max Sum Subarray
  36. Max Avg Sum of Two Subsequences
  37. Merge Overlapping Intervals
  38. Longest Balanced Subarray
  39. Longest Path in a Weighted Tree
  40. Generate Balanced Parentheses
  41. PostOrder Traversal Without Recursion

© 2022 – CSEstack.org. All Rights Reserved.

  • Home
  • Subscribe
  • Contribute Us
    • Share Your Interview Experience
  • Contact Us
  • About
    • About CSEstack
    • Campus Ambassador
  • Forum & Discus
  • Tools for Geek
  • LeaderBoard