Skip to main content

Find max number using k swap

In this article, we will discuss a problem where we need to find the maximum number that can be obtained by performing a maximum of K swaps on the digits of a given number. We will explain the problem statement, provide a suitable example, present the pseudocode algorithm with explanations, and analyze the resultant output. Let's dive in!

Problem Statement

Given a number and the maximum number of swaps allowed (K), we need to find the maximum number that can be obtained by swapping any two digits of the given number at most K times.

Example

Let's consider the number 7898941 and assume we are allowed to perform a maximum of 2 swaps. The goal is to find the maximum number that can be obtained.

Step 1:

Initially, we have the number 7898941.

Step 2:

We perform the first swap between the digits 8 and 9, resulting in the number 9898741.

Step 3:

We perform the second swap between the digits 4 and 9, resulting in the maximum number 9988741.

Therefore, the maximum number that can be obtained by performing at most 2 swaps on the number 7898941 is 9988741.

Pseudocode Algorithm

Let's explain the algorithm to solve the problem using pseudocode: 


function copyValue(num[], result[], n):
	for i = 0 to n-1:
		result[i] = num[i]

function isBigger(num[], result[], n):
	for i = 0 to n-1:
		if num[i] > result[i]:
			return 1
		else if num[i] < result[i]:
			return 0
	return 0

function swap(num[], i, j):
	temp = num[i]
	num[i] = num[j]
	num[j] = temp

function maximizeBySwap(num[], result[], n, k):
	if k = 0:
		return

	for i = 0 to n-2:
		for j = i+1 to n-1:
			if num[i] < num[j]:
				swap(num, i, j)
				if isBigger(num, result, n):
					copyValue(num, result, n)
				maximizeBySwap(num, result, n, k-1)
				swap(num, i, j)

function maximize(num[], n, k):
	if k ≤ 0:
		return

	result[n]
	copyValue(num, result, n)
	maximizeBySwap(num, result, n, k)

	print "Given number: " + num
	print "Swap by: " + k
	print "Result: " + result

main:
	num[] = "7898941"
	n = length(num)
	maximize(num, n, 2)
	maximize(num, n, 1)

Explanation of Pseudocode

The algorithm consists of several functions to handle different tasks:

  • copyValue(): Copies the values from one array to another.
  • isBigger(): Compares two arrays to check if the first one is greater than the second one.
  • swap(): Interchanges the values of two elements in an array.
  • maximizeBySwap(): Recursively finds the maximum number by performing swaps and tracks the current maximum number.
  • maximize(): Initializes the result array and calls maximizeBySwap() to find the maximum number.
  • main(): Initializes the input number and calls maximize() with different values of K.

The maximize() function is the main entry point, which initializes the result array and calls maximizeBySwap() to find the maximum number. It then prints the given number, the number of swaps, and the resulting maximum number.

Program Solution

// C program  
// Find max number using k swap
#include <stdio.h>

// Copy element value
void copyValue(char num[], char result[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		result[i] = num[i];
	}
}
// Check whether given num is greater than result
int isBigger(char num[], char result[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		if (num[i] > result[i])
		{
			return 1;
		}
		else if (num[i] < result[i])
		{
			return 0;
		}
	}
	// When if is equal
	return 0;
}
// Interchange the value of given two elements
void swap(char num[], int i, int j)
{
	char temp = num[i];
	num[i] = num[j];
	num[j] = temp;
}
// Maximize number by k swap
void maximizeBySwap(char num[], char result[], int n, int k)
{
	if (k == 0)
	{
		return;
	}
	// Loop controlling variables
	int i = 0;
	int j = 0;
	// Outer loop
	for (i = 0; i < n - 1; ++i)
	{
		// Inner loop
		for (j = i + 1; j < n; ++j)
		{
			if (num[i] < num[j])
			{
				swap(num, i, j);
				if (isBigger(num, result, n))
				{
					// Get new result
					copyValue(num, result, n);
				}
				maximizeBySwap(num, result, n, k - 1);
				swap(num, i, j);
			}
		}
	}
}
// Handles the request of maximize number in given swap
void maximize(char num[], int n, int k)
{
	if (k <= 0)
	{
		// Invalid swap
		return;
	}
	// Use to store result
	char result[n];
	// Copy element
	copyValue(num, result, n);
	maximizeBySwap(num, result, n, k);
	// Display result
	printf("\n Given number : %s", num);
	printf("\n Swap by : %d", k);
	printf("\n Result  : %s ", result);
}
int main()
{
	char num[] = "7898941";
	int n = sizeof(num) / sizeof(num[0]) - 1;
	maximize(num, n, 2);
	maximize(num, n, 1);
	return 0;
}

Output

 Given number : 7898941
 Swap by : 2
 Result  : 9988741
 Given number : 7898941
 Swap by : 1
 Result  : 9898741
/*
  Java Program for
  Find max number using k swap
*/
class Swapping
{
	// Copy element value
	public void copyValue(char[] num, char[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			result[i] = num[i];
		}
	}
	// Check whether given num is greater than result
	public boolean isBigger(char[] num, char[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			if (num[i] > result[i])
			{
				return true;
			}
			else if (num[i] < result[i])
			{
				return false;
			}
		}
		// When if is equal
		return false;
	}
	// Interchange the value of given two elements
	public void swap(char[] num, int i, int j)
	{
		char temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	// Maximize number by k swap
	public void maximizeBySwap(char[] num, char[] result, int n, int k)
	{
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Outer loop
		for (i = 0; i < n - 1; ++i)
		{
			// Inner loop
			for (j = i + 1; j < n; ++j)
			{
				if (num[i] < num[j])
				{
					swap(num, i, j);
					if (isBigger(num, result, n))
					{
						// Get new result
						copyValue(num, result, n);
					}
					maximizeBySwap(num, result, n, k - 1);
					swap(num, i, j);
				}
			}
		}
	}
	// Handles the request of maximize number in given swap
	public void maximize(String str, int n, int k)
	{
		if (k <= 0)
		{
			// Invalid swap
			return;
		}
		// Use to store result
		char[] result = new char[n];
      	char[] num = new char[n];
		for (int i = 0; i < n; i++)
		{
			result[i] = str.charAt(i);
            num[i] = str.charAt(i);
		}
		maximizeBySwap(num, result, n, k);
		String ans = new String(result);
		// Display result
		System.out.print("\n Given number : " + str);
		System.out.print("\n Swap by : " + k);
		System.out.print("\n Result : " + ans);
	}
	public static void main(String[] args)
	{
		Swapping task = new Swapping();
		String str = "7898941";
		int n = str.length();
		// Test Case
		// n = 2
		task.maximize(str, n, 2);
		// n = 1
		task.maximize(str, n, 1);
	}
}

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
// Include header file
#include <iostream>
#include<string.h>
using namespace std;
/*
  C++ Program for
  Find max number using k swap
*/
class Swapping
{
	public:
		// Copy element value
		void copyValue(char num[], char result[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				result[i] = num[i];
			}
		}
	// Check whether given num is greater than result
	bool isBigger(char num[], char result[], int n)
	{
		// When if is equal
		for (int i = 0; i < n; ++i)
		{
			if (num[i] > result[i])
			{
				return true;
			}
			else if (num[i] < result[i])
			{
				return false;
			}
		}
		return false;
	}
	// Interchange the value of given two elements
	void swap(char num[], int i, int j)
	{
		char temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	// Maximize number by k swap
	void maximizeBySwap(char num[], char result[], int n, int k)
	{
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Outer loop
		for (i = 0; i < n - 1; ++i)
		{
			// Inner loop
			for (j = i + 1; j < n; ++j)
			{
				if (num[i] < num[j])
				{
					this->swap(num, i, j);
					if (this->isBigger(num, result, n))
					{
						// Get new result
						this->copyValue(num, result, n);
					}
					this->maximizeBySwap(num, result, n, k - 1);
					this->swap(num, i, j);
				}
			}
		}
	}
	// Handles the request of maximize number in given swap
	void maximize(string str, int n, int k)
	{
		// Invalid swap
		if (k <= 0)
		{
			return;
		}
		// Use to store result
		char result[n];
		char num[n];
		// Copy value
		for (int i = 0; i < n; i++)
		{
			result[i] = str[i];
			num[i]    = str[i];
		}
		this->maximizeBySwap(num, result, n, k);
		// Display result
		cout << "\n Given number : " << str;
		cout << "\n Swap by : " << k;
		cout << "\n Result : " << result;
	}
};
int main()
{
	Swapping task = Swapping();
	string str = "7898941";
	int n = str.size();
	// Test Case
	// n = 2
	task.maximize(str, n, 2);
	// n = 1
	task.maximize(str, n, 1);
	return 0;
}

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
// Include namespace system
using System;
/*
  C# Program for
  Find max number using k swap
*/
public class Swapping
{
	// Copy element value
	public void copyValue(char[] num, char[] result, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			result[i] = num[i];
		}
	}
	// Check whether given num is greater than result
	public Boolean isBigger(char[] num, char[] result, int n)
	{
		// When if is equal
		for (int i = 0; i < n; ++i)
		{
			if (num[i] > result[i])
			{
				return true;
			}
			else if (num[i] < result[i])
			{
				return false;
			}
		}
		return false;
	}
	// Interchange the value of given two elements
	public void swap(char[] num, int i, int j)
	{
		char temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	// Maximize number by k swap
	public void maximizeBySwap(char[] num, char[] result, int n, int k)
	{
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		int i = 0;
		int j = 0;
		// Outer loop
		for (i = 0; i < n - 1; ++i)
		{
			// Inner loop
			for (j = i + 1; j < n; ++j)
			{
				if (num[i] < num[j])
				{
					swap(num, i, j);
					if (isBigger(num, result, n))
					{
						// Get new result
						copyValue(num, result, n);
					}
					maximizeBySwap(num, result, n, k - 1);
					swap(num, i, j);
				}
			}
		}
	}
	// Handles the request of maximize number in given swap
	public void maximize(String str, int n, int k)
	{
		// Invalid swap
		if (k <= 0)
		{
			return;
		}
		// Use to store result
		char[] result = new char[n];
		char[] num = new char[n];
		// Copy value
		for (int i = 0; i < n; i++)
		{
			result[i] = str[i];
			num[i] = str[i];
		}
		maximizeBySwap(num, result, n, k);
		String ans = new String(result);
		// Display result
		Console.Write("\n Given number : " + str);
		Console.Write("\n Swap by : " + k);
		Console.Write("\n Result : " + ans);
	}
	public static void Main(String[] args)
	{
		Swapping task = new Swapping();
		String str = "7898941";
		int n = str.Length;
		// Test Case
		// n = 2
		task.maximize(str, n, 2);
		// n = 1
		task.maximize(str, n, 1);
	}
}

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
<?php
/*
  Php Program for
  Find max number using k swap
*/
class Swapping
{
	// Copy element value
	public	function copyValue( & $num, & $result, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			$result[$i] = $num[$i];
		}
	}
	// Check whether given num is greater than result
	public	function isBigger( & $num, & $result, $n)
	{
		// When if is equal
		for ($i = 0; $i < $n; ++$i)
		{
			if (ord($num[$i]) > ord($result[$i]))
			{
				return true;
			}
			else if (ord($num[$i]) < ord($result[$i]))
			{
				return false;
			}
		}
		return false;
	}
	// Interchange the value of given two elements
	public	function swap( & $num, $i, $j)
	{
		$temp = $num[$i];
		$num[$i] = $num[$j];
		$num[$j] = $temp;
	}
	// Maximize number by k swap
	public	function maximizeBySwap( & $num, & $result, $n, $k)
	{
		if ($k == 0)
		{
			return;
		}
		// Loop controlling variables
		$i = 0;
		$j = 0;
		// Outer loop
		for ($i = 0; $i < $n - 1; ++$i)
		{
			// Inner loop
			for ($j = $i + 1; $j < $n; ++$j)
			{
				if (ord($num[$i]) < ord($num[$j]))
				{
					$this->swap($num, $i, $j);
					if ($this->isBigger($num, $result, $n))
					{
						// Get new result
						$this->copyValue($num, $result, $n);
					}
					$this->maximizeBySwap($num, $result, $n, $k - 1);
					$this->swap($num, $i, $j);
				}
			}
		}
	}
	// Handles the request of maximize number in given swap
	public	function maximize($str, $n, $k)
	{
		// Invalid swap
		if ($k <= 0)
		{
			return;
		}
		$i = 0;
		// Use to store result
		$result = array_fill(0, $n, ' ');
		$num = array_fill(0, $n, ' ');
		for ($i = 0; $i < $n; $i++)
		{
			$result[$i] = $str[$i];
			$num[$i] = $str[$i];
		}
		$this->maximizeBySwap($num, $result, $n, $k);
		$ans = "";
		for ($i = 0; $i < $n; ++$i)
		{
			$ans = $ans . $result[$i];
		}
		// Display result
		echo "\n Given number : ". $str;
		echo "\n Swap by : ". $k;
		echo "\n Result : ". $ans;
	}
}

function main()
{
	$task = new Swapping();
	$str = "7898941";
	$n = strlen($str);
	// Test Case
	// n = 2
	$task->maximize($str, $n, 2);
	// n = 1
	$task->maximize($str, $n, 1);
}
main();

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
/*
  Node Js Program for
  Find max number using k swap
*/
class Swapping
{
	// Copy element value
	copyValue(num, result, n)
	{
		for (var i = 0; i < n; ++i)
		{
			result[i] = num[i];
		}
	}
	// Check whether given num is greater than result
	isBigger(num, result, n)
	{
		// When if is equal
		for (var i = 0; i < n; ++i)
		{
			if ((num[i]).charCodeAt(0) > (result[i]).charCodeAt(0))
			{
				return true;
			}
			else if ((num[i]).charCodeAt(0) < (result[i]).charCodeAt(0))
			{
				return false;
			}
		}
		return false;
	}
	// Interchange the value of given two elements
	swap(num, i, j)
	{
		var temp = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	// Maximize number by k swap
	maximizeBySwap(num, result, n, k)
	{
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		var i = 0;
		var j = 0;
		// Outer loop
		for (i = 0; i < n - 1; ++i)
		{
			// Inner loop
			for (j = i + 1; j < n; ++j)
			{
				if ((num[i]).charCodeAt(0) < (num[j]).charCodeAt(0))
				{
					this.swap(num, i, j);
					if (this.isBigger(num, result, n))
					{
						// Get new result
						this.copyValue(num, result, n);
					}
					this.maximizeBySwap(num, result, n, k - 1);
					this.swap(num, i, j);
				}
			}
		}
	}
	// Handles the request of maximize number in given swap
	maximize(str, n, k)
	{
		// Invalid swap
		if (k <= 0)
		{
			return;
		}
		var i = 0;
		// Use to store result
		var result = Array(n).fill(' ');
		var num = Array(n).fill(' ');
		for (i = 0; i < n; i++)
		{
			result[i] = str[i];
			num[i] = str[i];
		}
		this.maximizeBySwap(num, result, n, k);
		var ans = "";
		for (i = 0; i < n; ++i)
		{
			ans = ans + result[i];
		}
		// Display result
		process.stdout.write("\n Given number : " + str);
		process.stdout.write("\n Swap by : " + k);
		process.stdout.write("\n Result : " + ans);
	}
}

function main()
{
	var task = new Swapping();
	var str = "7898941";
	var n = str.length;
	// Test Case
	// n = 2
	task.maximize(str, n, 2);
	// n = 1
	task.maximize(str, n, 1);
}
main();

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
#   Python 3 Program for
#   Find max number using k swap

class Swapping :
	#  Copy element value
	def copyValue(self, num, result, n) :
		i = 0
		while (i < n) :
			result[i] = num[i]
			i += 1
		
	
	#  Check whether given num is greater than result
	def isBigger(self, num, result, n) :
		#  When if is equal
		i = 0
		while (i < n) :
			if (ord(num[i]) > ord(result[i])) :
				return True
			
			elif(ord(num[i]) < ord(result[i])) :
				return False
			
			i += 1
		
		return False
	
	#  Interchange the value of given two elements
	def swap(self, num, i, j) :
		temp = num[i]
		num[i] = num[j]
		num[j] = temp
	
	#  Maximize number by k swap
	def maximizeBySwap(self, num, result, n, k) :
		if (k == 0) :
			return
		
		#  Loop controlling variables
		i = 0
		j = 0
		#  Outer loop
		while (i < n - 1) :
			#  Inner loop
			j = i + 1
			while (j < n) :
				if (ord(num[i]) < ord(num[j])) :
					self.swap(num, i, j)
					if (self.isBigger(num, result, n)) :
						#  Get new result
						self.copyValue(num, result, n)
					
					self.maximizeBySwap(num, result, n, k - 1)
					self.swap(num, i, j)
				
				j += 1
			
			i += 1
		
	
	#  Handles the request of maximize number in given swap
	def maximize(self, str, n, k) :
		#  Invalid swap
		if (k <= 0) :
			return
		
		i = 0
		#  Use to store result
		result = [ ' '
		] * (n)
		num = [ ' '
		] * (n)
		while (i < n) :
			result[i] = str[i]
			num[i] = str[i]
			i += 1
		
		self.maximizeBySwap(num, result, n, k)
		ans = ""
		i = 0
		while (i < n) :
			ans = ans + result[i]
			i += 1
		
		#  Display result
		print("\n Given number : ", str, end = "")
		print("\n Swap by : ", k, end = "")
		print("\n Result : ", ans, end = "")
	

def main() :
	task = Swapping()
	str = "7898941"
	n = len(str)
	#  Test Case
	#  n = 2
	task.maximize(str, n, 2)
	#  n = 1
	task.maximize(str, n, 1)

if __name__ == "__main__": main()

Output

 Given number :  7898941
 Swap by :  2
 Result :  9988741
 Given number :  7898941
 Swap by :  1
 Result :  9898741
#   Ruby Program for
#   Find max number using k swap

class Swapping 
	#  Copy element value
	def copyValue(num, result, n) 
		i = 0
		while (i < n) 
			result[i] = num[i]
			i += 1
		end

	end

	#  Check whether given num is greater than result
	def isBigger(num, result, n) 
		#  When if is equal
		i = 0
		while (i < n) 
			if ((num[i]).ord > (result[i]).ord) 
				return true
			elsif((num[i]).ord < (result[i]).ord) 
				return false
			end

			i += 1
		end

		return false
	end

	#  Interchange the value of given two elements
	def swap(num, i, j) 
		temp = num[i]
		num[i] = num[j]
		num[j] = temp
	end

	#  Maximize number by k swap
	def maximizeBySwap(num, result, n, k) 
		if (k == 0) 
			return
		end

		#  Loop controlling variables
		i = 0
		j = 0
		#  Outer loop
		while (i < n - 1) 
			#  Inner loop
			j = i + 1
			while (j < n) 
				if ((num[i]).ord < (num[j]).ord) 
					self.swap(num, i, j)
					if (self.isBigger(num, result, n)) 
						#  Get new result
						self.copyValue(num, result, n)
					end

					self.maximizeBySwap(num, result, n, k - 1)
					self.swap(num, i, j)
				end

				j += 1
			end

			i += 1
		end

	end

	#  Handles the request of maximize number in given swap
	def maximize(str, n, k) 
		#  Invalid swap
		if (k <= 0) 
			return
		end

		i = 0
		#  Use to store result
		result = Array.new(n) { ' '
		}
		num = Array.new(n) { ' '
		}
		while (i < n) 
			result[i] = str[i]
			num[i] = str[i]
			i += 1
		end

		self.maximizeBySwap(num, result, n, k)
		ans = ""
		i = 0
		while (i < n) 
			ans = ans + result[i]
			i += 1
		end

		#  Display result
		print("\n Given number : ", str)
		print("\n Swap by : ", k)
		print("\n Result : ", ans)
	end

end

def main() 
	task = Swapping.new()
	str = "7898941"
	n = str.length()
	#  Test Case
	#  n = 2
	task.maximize(str, n, 2)
	#  n = 1
	task.maximize(str, n, 1)
end

main()

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
/*
  Scala Program for
  Find max number using k swap
*/
class Swapping
{
	// Copy element value
	def copyValue(num: Array[Character], result: Array[Character], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			result(i) = num(i);
			i += 1;
		}
	}
	// Check whether given num is greater than result
	def isBigger(num: Array[Character], result: Array[Character], n: Int): Boolean = {
		// When if is equal
		var i: Int = 0;
		while (i < n)
		{
			if (num(i) > result(i))
			{
				return true;
			}
			else if (num(i) < result(i))
			{
				return false;
			}
			i += 1;
		}
		return false;
	}
	// Interchange the value of given two elements
	def swap(num: Array[Character], i: Int, j: Int): Unit = {
		var temp: Char = num(i);
		num(i) = num(j);
		num(j) = temp;
	}
	// Maximize number by k swap
	def maximizeBySwap(num: Array[Character], result: Array[Character], n: Int, k: Int): Unit = {
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		// Outer loop
		while (i < n - 1)
		{
			// Inner loop
			j = i + 1;
			while (j < n)
			{
				if (num(i) < num(j))
				{
					this.swap(num, i, j);
					if (this.isBigger(num, result, n))
					{
						// Get new result
						this.copyValue(num, result, n);
					}
					this.maximizeBySwap(num, result, n, k - 1);
					this.swap(num, i, j);
				}
				j += 1;
			}
			i += 1;
		}
	}
	// Handles the request of maximize number in given swap
	def maximize(str: String, n: Int, k: Int): Unit = {
		// Invalid swap
		if (k <= 0)
		{
			return;
		}
		var i: Int = 0;
		// Use to store result
		var result: Array[Character] = Array.fill[Character](n)(' ');
		var num: Array[Character] = Array.fill[Character](n)(' ');
		while (i < n)
		{
			result(i) = str(i);
			num(i) = str(i);
			i += 1;
		}
		this.maximizeBySwap(num, result, n, k);
		var ans: String = "";
		i = 0;
		while (i < n)
		{
			ans = ans + result(i);
			i += 1;
		}
		// Display result
		print("\n Given number : " + str);
		print("\n Swap by : " + k);
		print("\n Result : " + ans);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Swapping = new Swapping();
		var str: String = "7898941";
		var n: Int = str.length();
		// Test Case
		// n = 2
		task.maximize(str, n, 2);
		// n = 1
		task.maximize(str, n, 1);
	}
}

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741
/*
  Swift 4 Program for
  Find max number using k swap
*/
class Swapping
{
	// Copy element value
	func copyValue(_ num: [Character], _ result: inout[Character], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			result[i] = num[i];
			i += 1;
		}
	}
	// Check whether given num is greater than result
	func isBigger(_ num: [Character], _ result: [Character], _ n: Int)->Bool
	{
		// When if is equal
		var i: Int = 0;
		while (i < n)
		{
			if (num[i] > result[i])
			{
				return true;
			}
			else if (num[i] < result[i])
			{
				return false;
			}
			i += 1;
		}
		return false;
	}
	// Interchange the value of given two elements
	func swap(_ num: inout[Character], _ i: Int, _ j: Int)
	{
		let temp: Character = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	// Maximize number by k swap
	func maximizeBySwap(_ num: inout[Character], _ result: inout[Character], _ n: Int, _ k: Int)
	{
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		var i: Int = 0;
		var j: Int = 0;
		// Outer loop
		while (i < n - 1)
		{
			// Inner loop
			j = i + 1;
			while (j < n)
			{
				if (num[i] < num[j])
				{
					self.swap(&num, i, j);
					if (self.isBigger(num, result, n))
					{
						// Get new result
						self.copyValue(num, &result, n);
					}
					self.maximizeBySwap(&num, &result, n, k - 1);
					self.swap(&num, i, j);
				}
				j += 1;
			}
			i += 1;
		}
	}
	// Handles the request of maximize number in given swap
	func maximize(_ str: String, _ n: Int, _ k: Int)
	{
		// Invalid swap
		if (k <= 0)
		{
			return;
		}
		var i: Int = 0;
		// Use to store result
		var result: [Character] = Array(str);
		var num: [Character]    = Array(str);
		
		self.maximizeBySwap(&num, &result, n, k);
		var ans: String = "";
		i = 0;
		while (i < n)
		{
			ans = ans + String(result[i]);
			i += 1;
		}
		// Display result
		print("\n Given number : ", str, terminator: "");
		print("\n Swap by : ", k, terminator: "");
		print("\n Result : ", ans, terminator: "");
	}
}
func main()
{
	let task: Swapping = Swapping();
	let str: String = "7898941";
	let n: Int = str.count;
	// Test Case
	// n = 2
	task.maximize(str, n, 2);
	// n = 1
	task.maximize(str, n, 1);
}
main();

Output

 Given number :  7898941
 Swap by :  2
 Result :  9988741
 Given number :  7898941
 Swap by :  1
 Result :  9898741
/*
  Kotlin Program for
  Find max number using k swap
*/
class Swapping
{
	// Copy element value
	fun copyValue(num: Array < Char > , result: Array < Char > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			result[i] = num[i];
			i += 1;
		}
	}
	// Check whether given num is greater than result
	fun isBigger(num: Array < Char > , result: Array < Char > , n: Int): Boolean
	{
		// When if is equal
		var i: Int = 0;
		while (i < n)
		{
			if (num[i] > result[i])
			{
				return true;
			}
			else if (num[i] < result[i])
			{
				return false;
			}
			i += 1;
		}
		return false;
	}
	// Interchange the value of given two elements
	fun swap(num: Array < Char > , i: Int, j: Int): Unit
	{
		var temp: Char = num[i];
		num[i] = num[j];
		num[j] = temp;
	}
	// Maximize number by k swap
	fun maximizeBySwap(num: Array < Char > , result: Array < Char > , n: Int, k: Int): Unit
	{
		if (k == 0)
		{
			return;
		}
		// Loop controlling variables
		var i: Int = 0;
		var j: Int ;
		// Outer loop
		while (i < n - 1)
		{
			// Inner loop
			j = i + 1;
			while (j < n)
			{
				if (num[i] < num[j])
				{
					this.swap(num, i, j);
					if (this.isBigger(num, result, n))
					{
						// Get new result
						this.copyValue(num, result, n);
					}
					this.maximizeBySwap(num, result, n, k - 1);
					this.swap(num, i, j);
				}
				j += 1;
			}
			i += 1;
		}
	}
	// Handles the request of maximize number in given swap
	fun maximize(str: String, n: Int, k: Int): Unit
	{
		// Invalid swap
		if (k <= 0)
		{
			return;
		}
		var i: Int = 0;
		// Use to store result
		var result: Array < Char > = Array(n){' '};
		var num: Array < Char > = Array(n){' '};
		while (i < n)
		{
			result[i] = str[i];
			num[i] = str[i];
			i += 1;
		}
		this.maximizeBySwap(num, result, n, k);
		var ans: String = "";
		i = 0;
		while (i < n)
		{
			ans = ans + result[i];
			i += 1;
		}
		// Display result
		print("\n Given number : " + str);
		print("\n Swap by : " + k);
		print("\n Result : " + ans);
	}
}
fun main(args: Array < String > ): Unit
{
	var task: Swapping = Swapping();
	var str: String = "7898941";
	var n: Int = str.count();
	// Test Case
	// n = 2
	task.maximize(str, n, 2);
	// n = 1
	task.maximize(str, n, 1);
}

Output

 Given number : 7898941
 Swap by : 2
 Result : 9988741
 Given number : 7898941
 Swap by : 1
 Result : 9898741

Resultant Output Explanation

The code snippet produces the following output: 


Given number: 7898941
Swap by: 2
Result: 9988741

Given number: 7898941
Swap by: 1
Result: 9898741

The first output shows the given number (7898941), the number of swaps (2), and the resulting maximum number (9988741) obtained after performing the swaps.

The second output shows the given number (7898941), the number of swaps (1), and the resulting maximum number (9898741) obtained after performing the swaps.

Time Complexity of the Code

The time complexity of the code depends on the number of digits in the given number and the maximum number of swaps allowed. Let's denote the number of digits as d and the maximum number of swaps as k.

The maximizeBySwap() function uses nested loops to iterate over all possible pairs of digits for swapping. Since there are d-1 digits in the number, the outer loop runs d-1 times, and the inner loop runs d-i times for each iteration of the outer loop (where i is the index of the outer loop). Therefore, the total number of iterations for the nested loops is: 


(d-1) + (d-2) + (d-3) + ... + 1 = d(d-1)/2

Since the maximizeBySwap() function is called recursively within the inner loop, the total number of recursive calls can be approximated as k * d(d-1)/2

Last updated on by Kalkicode




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment