Find Next Higher Permutation of a Given Number

Problem – Find the next higher permutation of a given number. If it doesn’t exist, print ‘-1’.

Example – Number – 32876 –> next higher permutation = 36278
Number – 134 —> next higher permutation = 143
Number – 4321 —> next higher permutation doesn’t exist. Print -1

Input – A number ‘n’ as a string.

Output – Next higher permutation or -1, according to the result.

Solution:


 int main()
{
	string s1;
	getline(cin, s1);
	vector <char> v; int check =0;

	for (int i = 0; i < s1.length(); i++)
	{
		v.push_back(s1[i]);
	}
	
	int j;
	int index1, index2;

	for ( j = v.size() - 1; j > 0; j--)
		{
			if (v[j-1] < v[j])
			{
				index1 = j - 1;
				check = 1;       //there exists a permutation flag
				break;
			}
		}
		if (check == 0)
		{ 
			cout << "-1";             //solution doesn't exist
			return false;
		}

		for (int i = v.size() - 1; i > index1; i--)
		{
			if (v[i] > v[index1])
			{
				index2 = i;
				break;
			}
		}
		 
		swap(v[index1], v[index2]);              
		reverse(v.begin() + index1 + 1, v.end());


	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i];
	}

		_getch();
		return 0;
}


Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s