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 callsmaximizeBySwap()
to find the maximum number.main()
: Initializes the input number and callsmaximize()
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
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