Posted on by Kalkicode
Code Backtracking

Find all subsequences of string which divisible by k

Here given code implementation process.

/*
    Java program for
    Find all subsequences of string which divisible by k
*/
public class Divisibility
{
	int findDivisibleByK(String text, String output, 
                          int index, int remainder, int k, int n)
	{
		int result = 0;
		if (index != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			System.out.print("\n  " + output);
			// increase result
			result = 1;
		}
		// This loop controlling the subsequences process.
		for (int i = index; i < n; ++i)
		{
			// Recursively finding the subsequence
			result += findDivisibleByK(
              text, output + text.charAt(i), i + 1 , 
              ((remainder * 10) + (text.charAt(i) - '0')) % k, k, n);
		}
		return result;
	}
	public void divideByK(String text, int k)
	{
		int n = text.length();
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		System.out.print("\n  Given Number : " + text);
		// Display given k
		System.out.print("\n  Given K : " + k);
		// Find all subsequences which is divisible by k
		int result = findDivisibleByK(text, "", 0, 0, k, n);
		// Display calculated  number of result
		System.out.println("\n  Total result : " + result);
	}
	public static void main(String[] args)
	{
		Divisibility task = new Divisibility();
		// Test A
		// String Number : 247543
		// k = 3
		task.divideByK("247543", 3);
		// Test B
		// String Number 12324
		// k = 4
		task.divideByK("12324", 4);
		// Test B
		// String Number 634180725
		// k = 43
		task.divideByK("634180725", 43);
	}
}

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
// Include header file
#include <iostream>
#include <string>

using namespace std;
/*
    C++ program for
    Find all subsequences of string which divisible by k
*/
class Divisibility
{
	public: int findDivisibleByK(
      string text, string output, 
      int index, int remainder, int k, int n)
	{
		int result = 0;
		if (index != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			cout << "\n  " << output;
			// increase result
			result = 1;
		}
		// This loop controlling the subsequences process.
		for (int i = index; i < n; ++i)
		{
			// Recursively finding the subsequence
			result += this->findDivisibleByK(
              text, output  +  (text[i]), i + 1, 
              ((remainder *10) + (text[i] - '0')) % k, k, n);
		}
		return result;
	}
	void divideByK(string text, int k)
	{
		int n = text.length();
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		cout << "\n  Given Number : " << text;
		// Display given k
		cout << "\n  Given K : " << k;
		// Find all subsequences which is divisible by k
		int result = this->findDivisibleByK(text, "", 0, 0, k, n);
		// Display calculated  number of result
		cout << "\n  Total result : " << result << endl;
	}
};
int main()
{
	Divisibility *task = new Divisibility();
	// Test A
	// String Number : 247543
	// k = 3
	task->divideByK("247543", 3);
	// Test B
	// String Number 12324
	// k = 4
	task->divideByK("12324", 4);
	// Test B
	// String Number 634180725
	// k = 43
	task->divideByK("634180725", 43);
	return 0;
}

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
// Include namespace system
using System;
/*
    Csharp program for
    Find all subsequences of string which divisible by k
*/
public class Divisibility
{
	int findDivisibleByK(
  		String text, String output, 
   		int index, int remainder, int k, int n)
	{
		int result = 0;
		if (index != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			Console.Write("\n  " + output);
			// increase result
			result = 1;
		}
		// This loop controlling the subsequences process.
		for (int i = index; i < n; ++i)
		{
			// Recursively finding the subsequence
			result += this.findDivisibleByK(
              text, output + text[i], i + 1, 
              ((remainder * 10) + (text[i] - '0')) % k, k, n);
		}
		return result;
	}
	public void divideByK(String text, int k)
	{
		int n = text.Length;
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		Console.Write("\n  Given Number : " + text);
		// Display given k
		Console.Write("\n  Given K : " + k);
		// Find all subsequences which is divisible by k
		int result = this.findDivisibleByK(text, "", 0, 0, k, n);
		// Display calculated  number of result
		Console.WriteLine("\n  Total result : " + result);
	}
	public static void Main(String[] args)
	{
		Divisibility task = new Divisibility();
		// Test A
		// String Number : 247543
		// k = 3
		task.divideByK("247543", 3);
		// Test B
		// String Number 12324
		// k = 4
		task.divideByK("12324", 4);
		// Test B
		// String Number 634180725
		// k = 43
		task.divideByK("634180725", 43);
	}
}

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
package main
import "fmt"
/*
    Go program for
    Find all subsequences of string which divisible by k
*/

func findDivisibleByK(text string, 
	output string, index int, 
	remainder int, k int, n int) int {
	var result int = 0
	if index != 0 && remainder % k == 0 {
		// Display of subsequences which is divisible by k
		fmt.Print("\n  ", output)
		// increase result
		result = 1
	}
	// This loop controlling the subsequences process.
	for i := index ; i < n ; i++ {
		// Recursively finding the subsequence
		result += findDivisibleByK(text, output + string(text[i]), i + 1, 
			((remainder * 10) + (int(text[i]) - 48)) % k, k, n)
	}
	return result
}
func divideByK(text string, k int) {
	var n int = len(text)
	if k <= 0 || n == 0 {
		return
	}
	// Display given number
	fmt.Print("\n  Given Number : ", text)
	// Display given k
	fmt.Print("\n  Given K : ", k)
	// Find all subsequences which is divisible by k
	var result int = findDivisibleByK(text, "", 0, 0, k, n)
	// Display calculated  number of result
	fmt.Println("\n  Total result : ", result)
}
func main() {
	// Test A
	// String Number : 247543
	// k = 3
	divideByK("247543", 3)
	// Test B
	// String Number 12324
	// k = 4
	divideByK("12324", 4)
	// Test B
	// String Number 634180725
	// k = 43
	divideByK("634180725", 43)
}

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
<?php
/*
    Php program for
    Find all subsequences of string which divisible by k
*/
class Divisibility
{
	function findDivisibleByK(
  		$text, $output, $index, $remainder, $k, $n)
	{
		$result = 0;
		if ($index != 0 && $remainder % $k == 0)
		{
			// Display of subsequences which is divisible by k
			echo("\n  ".$output);
			// increase result
			$result = 1;
		}
		// This loop controlling the subsequences process.
		for ($i = $index; $i < $n; ++$i)
		{
			// Recursively finding the subsequence
			$result += $this->findDivisibleByK(
              $text, $output.strval($text[$i]), $i + 1, 
              (($remainder * 10) + (ord($text[$i]) - ord('0'))) % $k, 
              $k, $n);
		}
		return $result;
	}
	public	function divideByK($text, $k)
	{
		$n = strlen($text);
		if ($k <= 0 || $n == 0)
		{
			return;
		}
		// Display given number
		echo("\n  Given Number : ".$text);
		// Display given k
		echo("\n  Given K : ".$k);
		// Find all subsequences which is divisible by k
		$result = $this->findDivisibleByK($text, "", 0, 0, $k, $n);
		// Display calculated  number of result
		echo("\n  Total result : ".$result.
			"\n");
	}
}

function main()
{
	$task = new Divisibility();
	// Test A
	// String Number : 247543
	// k = 3
	$task->divideByK("247543", 3);
	// Test B
	// String Number 12324
	// k = 4
	$task->divideByK("12324", 4);
	// Test B
	// String Number 634180725
	// k = 43
	$task->divideByK("634180725", 43);
}
main();

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
/*
    Node JS program for
    Find all subsequences of string which divisible by k
*/
class Divisibility
{
	findDivisibleByK(text, output, index, remainder, k, n)
	{
		var result = 0;
		if (index != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			process.stdout.write("\n  " + output);
			// increase result
			result = 1;
		}
		// This loop controlling the subsequences process.
		for (var i = index; i < n; ++i)
		{
			// Recursively finding the subsequence
			result += this.findDivisibleByK(
              text, output + text.charAt(i), i + 1, 
              ((remainder * 10) + (text.charCodeAt(i) - 48)) % k, 
              k, n);
		}
		return result;
	}
	divideByK(text, k)
	{
		var n = text.length;
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		process.stdout.write("\n  Given Number : " + text);
		// Display given k
		process.stdout.write("\n  Given K : " + k);
		// Find all subsequences which is divisible by k
		var result = this.findDivisibleByK(text, "", 0, 0, k, n);
		// Display calculated  number of result
		console.log("\n  Total result : " + result);
	}
}

function main()
{
	var task = new Divisibility();
	// Test A
	// String Number : 247543
	// k = 3
	task.divideByK("247543", 3);
	// Test B
	// String Number 12324
	// k = 4
	task.divideByK("12324", 4);
	// Test B
	// String Number 634180725
	// k = 43
	task.divideByK("634180725", 43);
}
main();

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
#    Python 3 program for
#    Find all subsequences of string which divisible by k
class Divisibility :
	def findDivisibleByK(self, text, output, index, remainder, k, n) :
		result = 0
		if (index != 0 and remainder % k == 0) :
			#  Display of subsequences which is divisible by k
			print("\n  ", output, end = "")
			#  increase result
			result = 1
		
		i = index
		#  This loop controlling the subsequences process.
		while (i < n) :
			#  Recursively finding the subsequence
			result += self.findDivisibleByK(
              text, output + str(text[i]), i + 1, 
              ((remainder * 10) + (ord(text[i]) -48)) % k, k, n)
			i += 1
		
		return result
	
	def divideByK(self, text, k) :
		n = len(text)
		if (k <= 0 or n == 0) :
			return
		
		#  Display given number
		print("\n  Given Number : ", text, end = "")
		#  Display given k
		print("\n  Given K : ", k, end = "")
		#  Find all subsequences which is divisible by k
		result = self.findDivisibleByK(text, "", 0, 0, k, n)
		#  Display calculated  number of result
		print("\n  Total result : ", result)
	

def main() :
	task = Divisibility()
	#  Test A
	#  String Number : 247543
	#  k = 3
	task.divideByK("247543", 3)
	#  Test B
	#  String Number 12324
	#  k = 4
	task.divideByK("12324", 4)
	#  Test B
	#  String Number 634180725
	#  k = 43
	task.divideByK("634180725", 43)

if __name__ == "__main__": main()

Output

  Given Number :  247543
  Given K :  3
   24
   2475
   24753
   2454
   24543
   243
   27
   2754
   27543
   273
   24
   243
   474
   4743
   45
   453
   75
   753
   54
   543
   3
  Total result :  21

  Given Number :  12324
  Given K :  4
   12
   1232
   12324
   1224
   124
   132
   1324
   12
   124
   232
   2324
   224
   24
   32
   324
   24
   4
  Total result :  17

  Given Number :  634180725
  Given K :  43
   63425
   631025
   64180725
   6407
   645
   602
   341807
   34185
   3182
   387
   1075
   172
   0
  Total result :  13
#    Ruby program for
#    Find all subsequences of string which divisible by k
class Divisibility 
	def findDivisibleByK(text, output, index, remainder, k, n) 
		result = 0
		if (index != 0 && remainder % k == 0) 
			#  Display of subsequences which is divisible by k
			print("\n  ", output)
			#  increase result
			result = 1
		end

		i = index
		#  This loop controlling the subsequences process.
		while (i < n) 
			#  Recursively finding the subsequence
			result += self.findDivisibleByK(
              text, output + text[i].to_s, i + 1, 
              ((remainder * 10) + (text[i].ord - '0'.ord)) % k, k, n)
			i += 1
		end

		return result
	end

	def divideByK(text, k) 
		n = text.length
		if (k <= 0 || n == 0) 
			return
		end

		#  Display given number
		print("\n  Given Number : ", text)
		#  Display given k
		print("\n  Given K : ", k)
		#  Find all subsequences which is divisible by k
		result = self.findDivisibleByK(text, "", 0, 0, k, n)
		#  Display calculated  number of result
		print("\n  Total result : ", result, "\n")
	end

end

def main() 
	task = Divisibility.new()
	#  Test A
	#  String Number : 247543
	#  k = 3
	task.divideByK("247543", 3)
	#  Test B
	#  String Number 12324
	#  k = 4
	task.divideByK("12324", 4)
	#  Test B
	#  String Number 634180725
	#  k = 43
	task.divideByK("634180725", 43)
end

main()

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13

import scala.collection.mutable._;
/*
    Scala program for
    Find all subsequences of string which divisible by k
*/
class Divisibility()
{
	def findDivisibleByK(text: String, output: String, 
                         index: Int, remainder: Int, 
                         k: Int, n: Int): Int = {
		var result: Int = 0;
		if (index != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			print("\n  " + output);
			// increase result
			result = 1;
		}
		var i: Int = index;
		// This loop controlling the subsequences process.
		while (i < n)
		{
			// Recursively finding the subsequence
			result += findDivisibleByK(
              text, output + text.charAt(i).toString(), i + 1, 
              ((remainder * 10) + (text.charAt(i).toInt - '0'.toInt)) % k, 
              k, n);
			i += 1;
		}
		return result;
	}
	def divideByK(text: String, k: Int): Unit = {
		var n: Int = text.length();
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		print("\n  Given Number : " + text);
		// Display given k
		print("\n  Given K : " + k);
		// Find all subsequences which is divisible by k
		var result: Int = findDivisibleByK(text, "", 0, 0, k, n);
		// Display calculated  number of result
		println("\n  Total result : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Divisibility = new Divisibility();
		// Test A
		// String Number : 247543
		// k = 3
		task.divideByK("247543", 3);
		// Test B
		// String Number 12324
		// k = 4
		task.divideByK("12324", 4);
		// Test B
		// String Number 634180725
		// k = 43
		task.divideByK("634180725", 43);
	}
}

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13
import Foundation;
/*
    Swift 4 program for
    Find all subsequences of string which divisible by k
*/
class Divisibility
{
	func findDivisibleByK(_ text: [Character], 
                           _ output: String, 
                           _ index: Int, 
                           _ remainder: Int, 
                           _ k: Int, 
                           _ n: Int) -> Int
	{
		var result: Int = 0;
		if (index  != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			print("\n  ", output, terminator: "");
			// increase result
			result = 1;
		}
		var i: Int = index;
		// This loop controlling the subsequences process.
		while (i < n)
		{
			// Recursively finding the subsequence
			result += self.findDivisibleByK(
              text, output + String(text[i]), i + 1, 
              ((remainder * 10) + 
               (Int(UnicodeScalar(String(text[i]))!.value) - 48)) % k, k, n);
			i += 1;
		}
		return result;
	}
	func divideByK(_ text: String, _ k: Int)
	{
		let n: Int = text.count;
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		print("\n  Given Number : ", text, terminator: "");
		// Display given k
		print("\n  Given K : ", k, terminator: "");
		// Find all subsequences which is divisible by k
		let result: Int = self.findDivisibleByK(Array(text), "", 0, 0, k, n);
		// Display calculated  number of result
		print("\n  Total result : ", result);
	}
}
func main()
{
	let task: Divisibility = Divisibility();
	// Test A
	// String Number : 247543
	// k = 3
	task.divideByK("247543", 3);
	// Test B
	// String Number 12324
	// k = 4
	task.divideByK("12324", 4);
	// Test B
	// String Number 634180725
	// k = 43
	task.divideByK("634180725", 43);
}
main();

Output

  Given Number :  247543
  Given K :  3
   24
   2475
   24753
   2454
   24543
   243
   27
   2754
   27543
   273
   24
   243
   474
   4743
   45
   453
   75
   753
   54
   543
   3
  Total result :  21

  Given Number :  12324
  Given K :  4
   12
   1232
   12324
   1224
   124
   132
   1324
   12
   124
   232
   2324
   224
   24
   32
   324
   24
   4
  Total result :  17

  Given Number :  634180725
  Given K :  43
   63425
   631025
   64180725
   6407
   645
   602
   341807
   34185
   3182
   387
   1075
   172
   0
  Total result :  13
/*
    Kotlin program for
    Find all subsequences of string which divisible by k
*/
class Divisibility
{
	fun findDivisibleByK(
     text: String, output: String, index: Int, 
      remainder: Int, k: Int, n: Int): Int
	{
		var result: Int = 0;
		if (index != 0 && remainder % k == 0)
		{
			// Display of subsequences which is divisible by k
			print("\n  " + output);
			// increase result
			result = 1;
		}
		var i: Int = index;
		// This loop controlling the subsequences process.
		while (i < n)
		{
			// Recursively finding the subsequence
			result += this.findDivisibleByK(
              text, output + text.get(i).toString(), i + 1, 
              ((remainder * 10) + (text.get(i).toInt() - '0'.toInt())) % k,
              k, n);
			i += 1;
		}
		return result;
	}
	fun divideByK(text: String, k: Int): Unit
	{
		val n: Int = text.length;
		if (k <= 0 || n == 0)
		{
			return;
		}
		// Display given number
		print("\n  Given Number : " + text);
		// Display given k
		print("\n  Given K : " + k);
		// Find all subsequences which is divisible by k
		val result: Int = this.findDivisibleByK(text, "", 0, 0, k, n);
		// Display calculated  number of result
		println("\n  Total result : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Divisibility = Divisibility();
	// Test A
	// String Number : 247543
	// k = 3
	task.divideByK("247543", 3);
	// Test B
	// String Number 12324
	// k = 4
	task.divideByK("12324", 4);
	// Test B
	// String Number 634180725
	// k = 43
	task.divideByK("634180725", 43);
}

Output

  Given Number : 247543
  Given K : 3
  24
  2475
  24753
  2454
  24543
  243
  27
  2754
  27543
  273
  24
  243
  474
  4743
  45
  453
  75
  753
  54
  543
  3
  Total result : 21

  Given Number : 12324
  Given K : 4
  12
  1232
  12324
  1224
  124
  132
  1324
  12
  124
  232
  2324
  224
  24
  32
  324
  24
  4
  Total result : 17

  Given Number : 634180725
  Given K : 43
  63425
  631025
  64180725
  6407
  645
  602
  341807
  34185
  3182
  387
  1075
  172
  0
  Total result : 13

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





Categories
Relative Post