Divide and Conquer is a programming technique which makes the program more efficient to write. And this technique work on the concept of recursion to solve a problem step by step. Generally this technique work in three parts:- Divide:- Divide the problem into some subproblem. Conquer:- Conquer the subproblem by calling recursively until subproblem solved. Combine:- (Optional Step) Combine the subproblem solution. So, that we will get the final problem Solution. When the subproblems are large enough to solve recursively, we call the recursive case. Once the subproblem becomes small enough that we no longer recursive, we say that the recursion "bottom out" and that we have gotten down to the base case. Application of Divide and Conquer Quick Sort Strassen's algorithm for matrix multiplication Merge Sort Counting inversions Binary Search Finding Min and max Divide and Conquer Abstract Algorithm DAC(a,i,j) {
package numbertoword;
import java.util.*;
/**
*
* @author Rishabh
*/
public class NumberToWord {
/**
* @param args the command line arguments
*/
static int count,i=0,position=0;
static String arr[];
public void odd(){}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String number=sc.next();
int numlength=number.length();
if(numlength==11||numlength==10)
{ arr=new String[6];
arr[0]="Arab";
arr[1]="Crore";
arr[2]="Lakh";
arr[3]="Thousand";
arr[4]="Hundred";
arr[5]="";
}
if(numlength==9||numlength==8)
{ arr=new String[5];
arr[0]="Crore";
arr[1]="lakh";
arr[2]="thousand";
arr[3]="hundred";
arr[4]="";
}
if(numlength==7||numlength==6)
{ arr=new String[4];
arr[0]="lakh";
arr[1]="thousand";
arr[2]="hundred";
arr[3]="";
}
if(numlength==5||numlength==4)
{ arr=new String[3];
arr[0]="thousand";
arr[1]="hundred";
arr[2]="";
}
if(numlength==3)
{ arr=new String[2];
arr[0]="hundred";
arr[1]="";
}
while(numlength>0){
if((numlength%2==1)&&(numlength>3))
{
if('0'==number.charAt(position))
{
position=position+1;
numlength=numlength-1;
}
else{
if('1'==number.charAt(position))
{
String gnum=number.substring(position,position+2);
switch(gnum)
{
case "10":
System.out.print("Ten");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "11":
System.out.print("Eleven");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "12":
System.out.print("Twelve");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "13":
System.out.print("Thirteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "14":
System.out.print("Fourteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "15":
System.out.print("Fifteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "16":
System.out.print("Sixteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "17":
System.out.print("Seventeen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "18":
System.out.print("Eighteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "19":
System.out.print("Nineteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
default :
System.out.print("Some error occur");
}
}
else if('2'==number.charAt(position))
{
System.out.print("Twenty");
position=position+1;
numlength=numlength-1;
}
else if('3'==number.charAt(position))
{
System.out.print("Thirty");
position=position+1;
numlength=numlength-1;
}
else if('4'==number.charAt(position))
{
System.out.print("Forty");
position=position+1;
numlength=numlength-1;
}
else if('5'==number.charAt(position))
{
System.out.print("Fifty");
position=position+1;
numlength=numlength-1;
}
else if('6'==number.charAt(position))
{
System.out.print("Sixty");
position=position+1;
numlength=numlength-1;
}
else if('7'==number.charAt(position))
{
System.out.print("Seventy");
position=position+1;
numlength=numlength-1;
}
else if('8'==number.charAt(position))
{
System.out.print("Eighty");
position=position+1;
numlength=numlength-1;
}
else if('9'==number.charAt(position))
{
System.out.print("Ninty");
position=position+1;
numlength=numlength-1;
}
}
} else if(((numlength%2==0)&&(numlength>2))||numlength==3){
if('0'==number.charAt(position))
{
position=position+1;
numlength=numlength-1;
i++;
}
else if('1'==number.charAt(position))
{ System.out.print("one");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('2'==number.charAt(position))
{ System.out.print("Two");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('3'==number.charAt(position))
{ System.out.print("Three");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('4'==number.charAt(position))
{ System.out.print("Four");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('5'==number.charAt(position))
{ System.out.print("Five");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('6'==number.charAt(position))
{ System.out.print("Six");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('7'==number.charAt(position))
{ System.out.print("Seven");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('8'==number.charAt(position))
{ System.out.print("Eight");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('9'==number.charAt(position))
{ System.out.print("Nine");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
}else if(numlength<3){
if(numlength==2)
{
if('0'==number.charAt(position))
{
position=position+1;
numlength=numlength-1;
}
else{
if('1'==number.charAt(position))
{
String gnum=number.substring(position,position+2);
switch(gnum)
{
case "10":
System.out.print("Ten");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "11":
System.out.print("Eleven");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "12":
System.out.print("Twelve");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "13":
System.out.print("Thirteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "14":
System.out.print("Fourteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "15":
System.out.print("Fifteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "16":
System.out.print("Sixteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "17":
System.out.print("Seventeen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "18":
System.out.print("Eighteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
case "19":
System.out.print("Nineteen");
System.out.print(" "+arr[i]);
i++;
position=position+2;
numlength=numlength-2;
break;
default :
System.out.print("Some error occur");
}
}
else if('2'==number.charAt(position))
{
System.out.print("Twenty");
position=position+1;
numlength=numlength-1;
}
else if('3'==number.charAt(position))
{
System.out.print("Thirty");
position=position+1;
numlength=numlength-1;
}
else if('4'==number.charAt(position))
{
System.out.print("Forty");
position=position+1;
numlength=numlength-1;
}
else if('5'==number.charAt(position))
{
System.out.print("Fifty");
position=position+1;
numlength=numlength-1;
}
else if('6'==number.charAt(position))
{
System.out.print("Sixty");
position=position+1;
numlength=numlength-1;
}
else if('7'==number.charAt(position))
{
System.out.print("Seventy");
position=position+1;
numlength=numlength-1;
}
else if('8'==number.charAt(position))
{
System.out.print("Eighty");
position=position+1;
numlength=numlength-1;
}
else if('9'==number.charAt(position))
{
System.out.print("Ninty");
position=position+1;
numlength=numlength-1;
}
}
}if(numlength==1){
if('0'==number.charAt(position))
{
position=position+1;
numlength=numlength-1;
i++;
}
else if('1'==number.charAt(position))
{ System.out.print("one");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('2'==number.charAt(position))
{ System.out.print("Two");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('3'==number.charAt(position))
{ System.out.print("Three");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('4'==number.charAt(position))
{ System.out.print("Four");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('5'==number.charAt(position))
{ System.out.print("Five");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('6'==number.charAt(position))
{ System.out.print("Six");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('7'==number.charAt(position))
{ System.out.print("Seven");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('8'==number.charAt(position))
{ System.out.print("Eight");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}
else if('9'==number.charAt(position))
{ System.out.print("Nine");
System.out.print(" "+arr[i]);
i++;
position=position+1;
numlength=numlength-1;
}}
}
} }}
Comments
Post a Comment