Posted on by Kalkicode
Code Backtracking

# Find permutation of numbers divisible by k

In this article, we will discuss the problem of finding permutations of numbers that are divisible by a given integer, k. We will provide a detailed explanation of the problem, provide a suitable example to illustrate it, present an algorithm and pseudocode to solve the problem, and finally explain the output with the time complexity of the code.

## Introduction

The problem at hand is to find all the permutations of a given number such that each permutation is divisible by a given integer, k. We need to generate all possible permutations and check if they are divisible by k.

## Problem Statement

Given a positive integer, num, and another positive integer, k, we are required to find all the permutations of num such that each permutation is divisible by k.

### Example

Let's consider an example to better understand the problem. Suppose we have num = 16345 and k = 4. We need to find all the permutations of the digits in num that are divisible by 4.

The possible permutations in this case are:

• 13456
• 13564
• 14356
• 14536
• 15364
• 15436
• 31456
• 31564
• 34156
• 34516
• 35164
• 35416
• 43156
• 43516
• 41356
• 41536
• 45316
• 45136
• 53416
• 53164
• 54316
• 54136
• 51364
• 51436

Another example is when num = 120 and k = 3. The possible permutations in this case are:

• 120
• 102
• 210
• 201

## Algorithm and Pseudocode

1. Start by defining a function getNumber that converts a string to an integer.

``````int getNumber(char str[])
{
char *ptr;
return strtol(str, &ptr, 10);
}``````

2. Define a swap function that swaps two elements in an array.

``````void swap(char str[], int i, int j)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}``````

3. Define a recursive function divisiblePermutation to find all permutations of the digits.

``````void divisiblePermutation(char str[], int n, int length, int k)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != '0' && getNumber(str) % k == 0)
{
printf("%s\n", str);
}
return;
}
for (int i = n; i < length; ++i)
{
swap(str, i, n);
divisiblePermutation(str, n + 1, length, k);
swap(str, i, n);
}
}``````

4. Define a function digitLength to calculate the length of a number in digits.

``````int digitLength(int number)
{
int num = number;
int length = 0;
while (num != 0)
{
length++;
num /= 10;
}
return length;
}``````

5. Define the permutation function to handle the request and call the divisiblePermutation function.

``````void permutation(int number, int k)
{
if (number < 0)
{
return;
}
int length = digitLength(number);
if (length > 0)
{
char auxiliary[length];
sprintf(auxiliary, "%d", number);
printf("\nNumber %d, K = %d\n", number, k);
divisiblePermutation(auxiliary, 0, length, k);
}
}``````

6. In the main function, test the code by providing sample inputs.

``````int main()
{
int num = 16345;
int k = 4;
permutation(num, k);
num = 120;
k = 3;
permutation(num, k);

return 0;
}``````

## Code Solution

``````// C Program
// Find permutation of numbers divisible by k
#include <stdio.h>
#include <stdlib.h> // for strtol

int getNumber(char str[])
{
char *ptr;
return strtol(str, & ptr, 10);
}
//Swap two elements in given string
//i and j is location
void swap(char str[], int i, int j)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
void divisiblePermutation(char str[], int n, int length, int k)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != '0' && getNumber(str) % k == 0)
{
printf(" %s\n", str);
}
return;
}
for (int i = n; i < length; ++i)
{
//swap the array element
swap(str, i, n);
divisiblePermutation(str, n + 1, length, k);
//swap the array element
swap(str, i, n);
}
}
// Get the length of digits
int digitLength(int number)
{
int num = number;
int length = 0;
while (num != 0)
{
length++;
num /= 10;
}
return length;
}
// Handles the request to find divisible permutation
void permutation(int number, int k)
{
if (number < 0)
{
// When number is negative
return;
}
int length = digitLength(number);
if (length > 0)
{
char auxiliary[length];
// Convert number to str
sprintf(auxiliary, "%d", number);
// Given number
printf("\n Number %d , K = %d \n", number, k);
divisiblePermutation(auxiliary, 0, length, k);
}
}
int main()
{
int num = 16345;
int k = 4;
// Test Cases
permutation(num, k);
num = 120;
k = 3;
permutation(num, k);
return 0;
}``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````
``````/*
Java Program for
Find permutation of numbers divisible by k
*/
public class Permutation
{
public int getNumber(char[] str)
{
String text = new String(str);
return Integer.parseInt(text);
}
//Swap two elements in given string
//i and j is location
public void swap(char[] str, int i, int j)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
public void divisiblePermutation(char[] str, int n, int length, int k)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != '0' && getNumber(str) % k == 0)
{
String text = new String(str);
System.out.print(" " + text + "\n");
}
return;
}
for (int i = n; i < length; ++i)
{
//swap the array element
swap(str, i, n);
divisiblePermutation(str, n + 1, length, k);
//swap the array element
swap(str, i, n);
}
}
// Handles the request to find divisible permutation
public void findPermutation(int number, int k)
{
if (number < 0)
{
// When number is negative
return;
}
char[] auxiliary = String.valueOf(number).toCharArray();
int length = auxiliary.length;
// Given number
System.out.print("\n Number " + number + " , K = " + k + " \n");
divisiblePermutation(auxiliary, 0, length, k);
}
public static void main(String[] args)
{
int num = 16345;

int k  = 4;

// Test Cases

num = 120;
k = 3;
}
}``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````
``````// Include header file
#include <iostream>
#include <string.h>

using namespace std;
/*
C++ Program for
Find permutation of numbers divisible by k
*/
class Permutation
{
public:
int getNumber(char str[])
{
string s(str);
return atoi(s.c_str());
}
//Swap two elements in given string
//i and j is location
void swap(char str[], int i, int j)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
void divisiblePermutation(char str[], int n, int length, int k)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != '0' && this->getNumber(str) % k == 0)
{

cout << " " << str << "\n";
}
return;
}
for (int i = n; i < length; ++i)
{
//swap the array element
this->swap(str, i, n);
this->divisiblePermutation(str, n + 1, length, k);
//swap the array element
this->swap(str, i, n);
}
}
// Get the length of digits
int digitLength(int number)
{

int num = number;
int length = 0;
while(num!=0)
{
length ++;
num/=10;
}
return length;
}
// Handles the request to find divisible permutation
void findPermutation(int number, int k)
{
// When number is negative
if (number < 0)
{
return;
}

string text = to_string(number);
int length  = text.size();
// Given number
cout << "\n Number " << number << " , K = " << k << " \n";
char auxiliary[length];
strcpy(auxiliary,text.c_str());

this->divisiblePermutation(auxiliary, 0, length, k);
}
};
int main()
{
int num = 16345;
int k = 4;
// Test Cases
num = 120;
k = 3;
return 0;
}``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````
``````// Include namespace system
using System;
using System.Globalization;
/*
C# Program for
Find permutation of numbers divisible by k
*/
public class Permutation
{
public int getNumber(char[] str)
{
String text = new String(str);
return  int.Parse(text);
}
//Swap two elements in given string
//i and j is location
public void swap(char[] str, int i, int j)
{
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
public void divisiblePermutation(char[] str, int n, int length, int k)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != '0' && getNumber(str) % k == 0)
{
String text = new String(str);
Console.Write(" " + text + "\n");
}
return;
}
for (int i = n; i < length; ++i)
{
//swap the array element
swap(str, i, n);
divisiblePermutation(str, n + 1, length, k);
//swap the array element
swap(str, i, n);
}
}
// Handles the request to find divisible permutation
public void findPermutation(int number, int k)
{
// When number is negative
if (number < 0)
{
return;
}
char[] auxiliary = (""+number).ToCharArray();
int length = auxiliary.Length;
// Given number
Console.Write("\n Number " + number + " , K = " + k + " \n");
divisiblePermutation(auxiliary, 0, length, k);
}
public static void Main(String[] args)
{
int num = 16345;
int k = 4;
// Test Cases
num = 120;
k = 3;
}
}``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````
``````<?php
/*
Php Program for
Find permutation of numbers divisible by k
*/
class Permutation
{
public	function getNumber(\$str)
{
\$text = implode(\$str);
return intval(\$text);
}
//Swap two elements in given string
//i and j is location
public function swap( & \$str, \$i, \$j)
{
\$temp = \$str[\$i];
\$str[\$i] = \$str[\$j];
\$str[\$j] = \$temp;
}
// Find all permutation of number which is divisible by given k
public	function divisiblePermutation( & \$str, \$n, \$length, \$k)
{
if (\$n > \$length)
{
return;
}
if (\$n == \$length)
{
if (\$str[0] != '0' && \$this->getNumber(\$str) % \$k == 0)
{
echo " ".implode(\$str)."\n";
}
return;
}
for (\$i = \$n; \$i < \$length; ++\$i)
{
//swap the array element
\$this->swap(\$str, \$i, \$n);
\$this->divisiblePermutation(\$str, \$n + 1, \$length, \$k);
//swap the array element
\$this->swap(\$str, \$i, \$n);
}
}
// Handles the request to find divisible permutation
public	function findPermutation(\$number, \$k)
{
// When number is negative
if (\$number < 0)
{
return;
}
\$auxiliary = str_split("".\$number);
\$length = count(\$auxiliary);
// Given number
echo "\n Number ". \$number ." , K = ". \$k ." \n";
\$this->divisiblePermutation(\$auxiliary, 0, \$length, \$k);
}
}

function main()
{
\$num = 16345;
\$k = 4;
// Test Cases
\$num = 120;
\$k = 3;
}
main();``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````
``````/*
Node Js Program for
Find permutation of numbers divisible by k
*/
class Permutation
{
getNumber(str)
{
var text = str.join("");
return parseInt(text);
}
//Swap two elements in given string
//i and j is location
swap(str, i, j)
{
var temp = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
divisiblePermutation(str, n, length, k)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0]!= '0' && this.getNumber(str) % k == 0)
{

console.log(" " + (str.join("")));
}
return;
}
for (var i = n; i < length; ++i)
{
//swap the array element
this.swap(str, i, n);
this.divisiblePermutation(str, n + 1, length, k);
//swap the array element
this.swap(str, i, n);
}
}
// Handles the request to find divisible permutation
findPermutation(number, k)
{
// When number is negative
if (number < 0)
{
return;
}
var auxiliary = (number.toString()).split("");
var length = auxiliary.length;
// Given number
console.log(" Number " + number + " , K = " + k );
this.divisiblePermutation(auxiliary, 0, length, k);
}
}

function main()
{
var num = 16345;
var k = 4;
// Test Cases
num = 120;
k = 3;
}
main();``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436
Number 120 , K = 3
120
102
210
201``````
``````#    Python 3 Program for
#    Find permutation of numbers divisible by k

class Permutation :
def getNumber(self, str) :
sperator = ""
text = sperator.join(str)
return int(text)

# Swap two elements in given string
# i and j is location
def swap(self, str, i, j) :
temp = str[i]
str[i] = str[j]
str[j] = temp

#  Find all permutation of number which is divisible by given k
def divisiblePermutation(self, str, n, length, k) :
if (n > length) :
return

if (n == length) :
if (str[0] != '0' and self.getNumber(str) % k == 0) :
print(" ","".join(str) )

return

i = n
while (i < length) :
# swap the array element
self.swap(str, i, n)
self.divisiblePermutation(str, n + 1, length, k)
# swap the array element
self.swap(str, i, n)
i += 1

#  Handles the request to find divisible permutation
def findPermutation(self, number, k) :
#  When number is negative
if (number < 0) :
return

auxiliary = list(str(number))
length = len(auxiliary)
#  Given number
print("\n Number ", number ," , K = ", k ," ")
self.divisiblePermutation(auxiliary, 0, length, k)

def main() :
num = 16345
k = 4
#  Test Cases
num = 120
k = 3

if __name__ == "__main__": main()``````

#### Output

`````` Number  16345  , K =  4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number  120  , K =  3
120
102
210
201``````
``````#    Ruby Program for
#    Find permutation of numbers divisible by k

class Permutation
def getNumber(str)
return (str.join("")).to_i
end

# Swap two elements in given string
# i and j is location
def swap(str, i, j)
temp = str[i]
str[i] = str[j]
str[j] = temp
end

#  Find all permutation of number which is divisible by given k
def divisiblePermutation(str, n, length, k)
if (n > length)
return
end

if (n == length)
if (str[0] != '0' && self.getNumber(str) % k == 0)
text = (str.join(""))
print(" ", text ,"\n")
end

return
end

i = n
while (i < length)
# swap the array element
self.swap(str, i, n)
self.divisiblePermutation(str, n + 1, length, k)
# swap the array element
self.swap(str, i, n)
i += 1
end

end

#  Handles the request to find divisible permutation
def findPermutation(number, k)
#  When number is negative
if (number < 0)
return
end

auxiliary = number.to_s.split(//)
length = auxiliary.length
#  Given number
print("\n Number ", number ," , K = ", k ," \n")
self.divisiblePermutation(auxiliary, 0, length, k)
end

end

def main()
num = 16345
k = 4
#  Test Cases
num = 120
k = 3
end

main()``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201
``````
``````/*
Scala Program for
Find permutation of numbers divisible by k
*/
class Permutation
{
def getNumber(str: Array[Char]): Int = {
return str.mkString("").toInt;
}
//Swap two elements in given string
//i and j is location
def swap(str: Array[Char], i: Int, j: Int): Unit = {
var temp: Char = str(i);
str(i) = str(j);
str(j) = temp;
}
// Find all permutation of number which is divisible by given k
def divisiblePermutation(str: Array[Char], n: Int, length: Int, k: Int): Unit = {
if (n > length)
{
return;
}
if (n == length)
{
if (str(0) != '0' && this.getNumber(str) % k == 0)
{
var text: String = str.mkString("");
print(" " + text + "\n");
}
return;
}
var i: Int = n;
while (i < length)
{
//swap the array element
this.swap(str, i, n);
this.divisiblePermutation(str, n + 1, length, k);
//swap the array element
this.swap(str, i, n);
i += 1;
}
}
// Handles the request to find divisible permutation
def findPermutation(number: Int, k: Int): Unit = {
// When number is negative
if (number < 0)
{
return;
}
var auxiliary = (number.toString).toCharArray();
var length: Int = auxiliary.length;
// Given number
print("\n Number " + number + " , K = " + k + " \n");
this.divisiblePermutation(auxiliary, 0, length, k);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Permutation = new Permutation();
var num: Int = 16345;
var k: Int = 4;
// Test Cases
num = 120;
k = 3;
}
}``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````
``````/*
Swift 4 Program for
Find permutation of numbers divisible by k
*/
class Permutation
{
func getNumber(_ str: [Character])->Int
{
let text: String = String(str);
return Int(text)!;
}
//Swap two elements in given string
//i and j is location
func swap(_ str: inout[Character], _ i: Int, _ j: Int)
{
let temp: Character = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
func divisiblePermutation(_ str: inout[Character], _ n: Int, _ length: Int, _ k: Int)
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != "0" && self.getNumber(str) % k == 0)
{
let text: String = String(str);
print(" ", text );
}
return;
}
var i: Int = n;
while (i < length)
{
//swap the array element
self.swap(&str, i, n);
self.divisiblePermutation(&str, n + 1, length, k);
//swap the array element
self.swap(&str, i, n);
i += 1;
}
}
// Handles the request to find divisible permutation
func findPermutation(_ number: Int, _ k: Int)
{
// When number is negative
if (number < 0)
{
return;
}
var auxiliary: [Character] = Array(String(number));
let length: Int = auxiliary.count;
// Given number
print("\n Number ", number ," , K = ", k ," ");
self.divisiblePermutation(&auxiliary, 0, length, k);
}
}
func main()
{
var num: Int = 16345;
var k: Int = 4;
// Test Cases
num = 120;
k = 3;
}
main();``````

#### Output

`````` Number  16345  , K =  4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number  120  , K =  3
120
102
210
201``````
``````/*
Kotlin Program for
Find permutation of numbers divisible by k
*/
class Permutation
{
fun getNumber(str: Array<Char> ): Int
{
var text: String = str.joinToString(separator = "");
return (text.toInt());
}
//Swap two elements in given string
//i and j is location
fun swap(str: Array<Char> , i: Int, j: Int): Unit
{
var temp: Char = str[i];
str[i] = str[j];
str[j] = temp;
}
// Find all permutation of number which is divisible by given k
fun divisiblePermutation(str: Array < Char > , n: Int, length: Int, k: Int): Unit
{
if (n > length)
{
return;
}
if (n == length)
{
if (str[0] != '0' && this.getNumber(str) % k == 0)
{
var text: String = str.joinToString(separator = "");
print(" " + text + "\n");
}
return;
}
var i: Int = n;
while (i < length)
{
//swap the array element
this.swap(str, i, n);
this.divisiblePermutation(str, n + 1, length, k);
//swap the array element
this.swap(str, i, n);
i += 1;
}
}
// Handles the request to find divisible permutation
fun findPermutation(number: Int, k: Int): Unit
{
// When number is negative
if (number < 0)
{
return;
}
var auxiliary = number.toString().toCharArray().toTypedArray();
var length: Int = auxiliary.count();
// Given number
print("\n Number " + number + " , K = " + k + " \n");
this.divisiblePermutation(auxiliary, 0, length, k);
}
}
fun main(args: Array <String> ): Unit
{
var num: Int = 16345;
var k: Int = 4;
// Test Cases
num = 120;
k = 3;
}``````

#### Output

`````` Number 16345 , K = 4
13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436

Number 120 , K = 3
120
102
210
201``````

## Output Explanation

For the first test case (num = 16345, k = 4), the output is:

``````13456
13564
14356
14536
15364
15436
31456
31564
34156
34516
35164
35416
43156
43516
41356
41536
45316
45136
53416
53164
54316
54136
51364
51436``````

These are all the possible permutations of the digits of 16345 that are divisible by 4.

For the second test case (num = 120, k = 3), the output is:

``````120
102
210
201``````

These are all the possible permutations of the digits of 120 that are divisible by 3.

## Time Complexity

The time complexity of this code is O(n!), where n is the number of digits in the given number. This is because we generate all possible permutations of the digits. As the number of digits increases, the number of permutations grows exponentially.

## 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