Posted on by Kalkicode
Code Backtracking

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)
{
String str = "7898941";
int n = str.length();
// Test Case
// n = 2
// n = 1
}
}

Output

Given number : 7898941
Swap by : 2
Result : 9988741
Given number : 7898941
Swap by : 1
Result : 9898741
#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()
{
string str = "7898941";
int n = str.size();
// Test Case
// n = 2
// 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)
{
String str = "7898941";
int n = str.Length;
// Test Case
// n = 2
// 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()
{
\$str = "7898941";
\$n = strlen(\$str);
// Test Case
// n = 2
// 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 str = "7898941";
var n = str.length;
// Test Case
// n = 2
// 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() :
str = "7898941"
n = len(str)
#  Test Case
#  n = 2
#  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()
str = "7898941"
n = str.length()
#  Test Case
#  n = 2
#  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
// 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 str: String = "7898941";
let n: Int = str.count;
// Test Case
// n = 2
// 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 str: String = "7898941";
var n: Int = str.count();
// Test Case
// n = 2
// 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

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.

Categories
Relative Post