Bob is playing with his ball destroyer robot. Initially, Bob has r
red balls, g green balls and b blue balls. The robot
will repeat the following 3-step program until there are no balls
left:
Source : Commented by a user named bob , later i found property of TopCoder , so i have am just sharing it to learning purpose , TopCoder Inc. holds all right on the problem statement .
|
Showing posts with label Interview Question. Show all posts
Showing posts with label Interview Question. Show all posts
Thursday, December 20, 2012
Find the color of the k-th ball (1-index based) that will be destroyed.
Sunday, June 12, 2011
WAP to Implement the hash Function For String Variable Which Act as a Key in hashTable
The String hash function
In the String class, for example, the hash code h of a string s of length n is calculated as
hash=a[0]*31^n-1+a[1]*31^n-2+........a[n-1]*31^0
or, in code,
int h = 0;
for (int i = 0; i < n; i++)
{
h = 31*h + s.charAt(i);
}
For example the hash code of hello uses the Unicode values of its characters
h e l l o
h e l l o
104 101 108 108 111(ASCII Values) to give the value 99162332=104*31^4+101*31^3+108*31^2+108*31^1+111
benefits of Doing This is that we won't get same hash values for anagram string e.g. hello & olhel, helol etc.
In general the arithmetic operations in such expressions will use 32-bit modular arithmetic ignoring overflow. For example Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
where Integer.MAX_VALUE =2147483647 Integer.MIN_VALUE =-2147483648 Note that, because of wraparound associated with modular arithmetic, the hash code could be negative, or even zero. It happened to be positive in this case because hello is a fairly short string. Thus, for example, the hash code for helloa, which is 31 times the hash code for hello plus 97, would not be , which is outside the range of 32-bit signed integers, but 3074032079-2^32=-1220935217 (which is in the range)
so After All The Basic & Efficient has Function For String Looks Like
int hash(String key)
{ int h = 0;
for (int i = 0; i < key.length; i++)
{
h = 31*h + s.charAt(i); }
if(h>INT_MAX)
return h-INT_MAX // or h % table_size
else if(h<INT_MIN)
return h+INT_MAX;
return h; //else return h
}
Another Hash Function Cloud be if consider string only combination of alpha-bates so base 26
if we simply use the sum or crc type hash function we will get the same hash value thus collision.
see hash function
int hash (String s)
{
int k = 0, m = 26;
for (int i=0; i < s.length(); i++)
k += (int)s.charAt (i);
return ( k%m );
}
it will return same hash value for all anagram string as explained above .
int hash(String s)
{
int k = 0, m = 26;
for (int i=0; i < s.length(); i++)
k += (int)s.charAt (i) + i*(int)s.charAt (i);
return ( k%m );
}
benefits of Doing This is that we won't get same hash values for anagram string e.g. hello &
olhel, helol etc.
Some other information on String Hash Function .
http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier
http://www.jchq.net/certkey/0902certkey.htm
Feel Free to Comment.
In the String class, for example, the hash code h of a string s of length n is calculated as
hash=a[0]*31^n-1+a[1]*31^n-2+........a[n-1]*31^0
or, in code,
int h = 0;
for (int i = 0; i < n; i++)
{
h = 31*h + s.charAt(i);
}
For example the hash code of hello uses the Unicode values of its characters
h e l l o
h e l l o
104 101 108 108 111(ASCII Values) to give the value 99162332=104*31^4+101*31^3+108*31^2+108*31^1+111
benefits of Doing This is that we won't get same hash values for anagram string e.g. hello & olhel, helol etc.
In general the arithmetic operations in such expressions will use 32-bit modular arithmetic ignoring overflow. For example Integer.MAX_VALUE + 1 = Integer.MIN_VALUE
where Integer.MAX_VALUE =2147483647 Integer.MIN_VALUE =-2147483648 Note that, because of wraparound associated with modular arithmetic, the hash code could be negative, or even zero. It happened to be positive in this case because hello is a fairly short string. Thus, for example, the hash code for helloa, which is 31 times the hash code for hello plus 97, would not be , which is outside the range of 32-bit signed integers, but 3074032079-2^32=-1220935217 (which is in the range)
so After All The Basic & Efficient has Function For String Looks Like
int hash(String key)
{ int h = 0;
for (int i = 0; i < key.length; i++)
{
h = 31*h + s.charAt(i); }
if(h>INT_MAX)
return h-INT_MAX // or h % table_size
else if(h<INT_MIN)
return h; //else return h
}
Another Hash Function Cloud be if consider string only combination of alpha-bates so base 26
if we simply use the sum or crc type hash function we will get the same hash value thus collision.
see hash function
int hash (String s)
{
int k = 0, m = 26;
for (int i=0; i < s.length(); i++)
k += (int)s.charAt (i);
return ( k%m );
}
it will return same hash value for all anagram string as explained above .
int hash(String s)
{
int k = 0, m = 26;
for (int i=0; i < s.length(); i++)
k += (int)s.charAt (i) + i*(int)s.charAt (i);
return ( k%m );
}
benefits of Doing This is that we won't get same hash values for anagram string e.g. hello &
olhel, helol etc.
Thursday, March 24, 2011
WAP to Find Mean,Median,Mod of Array
/***************************************************************
******* Program to find Mean,Median,and Mode *******
****************************************************************/
#define SIZE 100
#include
float mean_function(float[],int);
float median_function(float[],int);
float mode_function(float[],int);
int main()
{
int i,n,choice;
float array[SIZE],mean,median,mode;
printf("Enter No of Elements\n");
scanf("%d",&n);
printf("Enter Elements\n");
for(i=0;i
scanf("%f",&array[i]);
do
{
printf("\n\tEnter Choice\n\t1.Mean\n\t2.Median\n\t3.Mode\n4.Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
mean=mean_function(array,n);
printf("\n\tMean = %f\n",mean);
break;
case 2:
median=median_function(array,n);
printf("\n\tMedian = %f\n",median);
break;
case 3:
mode=mode_function(array,n);
printf("\n\tMode = %f\n",mode);
break;
case 4:
break;
default:
printf("Wrong Option");
break;
}
}while(choice!=4);
}
/***************************************************************
Function Name : mean_function
Purpose : to find mean
Input : array of elements,no of elements
Return Value : Mean
Return Type : Float
****************************************************************/
float mean_function(float array[],int n)
{
int i;
float sum=0;
for(i=0;i
sum=sum+array[i];
return (sum/n);
}
/***************************************************************
Function Name : median_function
Purpose : to find median
Input : array of elements,no of elements
Return Value : Median
Return Type : Float
****************************************************************/
float median_function(float a[],int n)
{
float temp;
int i,j;
for(i=0;i
for(j=i+1;j
if(a[i]>a[j])
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
if(n%2==0)
return (a[n/2]+a[n/2-1])/2;
else
return a[n/2];
}
float mode_function(float a[],int n)
{
return (3*median_function(a,n)-2*mean_function(a,n));
}
Output
————–
Enter Elements
2
3
4
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
1
Mean = 3.000000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
2
Median = 3.000000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
3
Mode = 3.000000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
4
——————-
Enter No of Elements
4
Enter Elements
9 8 7 6
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
1
Mean = 7.500000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
2
Median = 7.500000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
3
Mode = 7.500000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
4
******* Program to find Mean,Median,and Mode *******
****************************************************************/
#define SIZE 100
#include
float mean_function(float[],int);
float median_function(float[],int);
float mode_function(float[],int);
int main()
{
int i,n,choice;
float array[SIZE],mean,median,mode;
printf("Enter No of Elements\n");
scanf("%d",&n);
printf("Enter Elements\n");
for(i=0;i
scanf("%f",&array[i]);
do
{
printf("\n\tEnter Choice\n\t1.Mean\n\t2.Median\n\t3.Mode\n4.Exit");
scanf("%d",&choice);
switch(choice)
{
case 1:
mean=mean_function(array,n);
printf("\n\tMean = %f\n",mean);
break;
case 2:
median=median_function(array,n);
printf("\n\tMedian = %f\n",median);
break;
case 3:
mode=mode_function(array,n);
printf("\n\tMode = %f\n",mode);
break;
case 4:
break;
default:
printf("Wrong Option");
break;
}
}while(choice!=4);
}
/***************************************************************
Function Name : mean_function
Purpose : to find mean
Input : array of elements,no of elements
Return Value : Mean
Return Type : Float
****************************************************************/
float mean_function(float array[],int n)
{
int i;
float sum=0;
for(i=0;i
sum=sum+array[i];
return (sum/n);
}
/***************************************************************
Function Name : median_function
Purpose : to find median
Input : array of elements,no of elements
Return Value : Median
Return Type : Float
****************************************************************/
float median_function(float a[],int n)
{
float temp;
int i,j;
for(i=0;i
for(j=i+1;j
if(a[i]>a[j])
{
temp=a[j];
a[j]=a[i];
a[i]=temp;
}
}
if(n%2==0)
return (a[n/2]+a[n/2-1])/2;
else
return a[n/2];
}
float mode_function(float a[],int n)
{
return (3*median_function(a,n)-2*mean_function(a,n));
}
Output
————–
Enter Elements
2
3
4
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
1
Mean = 3.000000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
2
Median = 3.000000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
3
Mode = 3.000000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
4
——————-
Enter No of Elements
4
Enter Elements
9 8 7 6
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
1
Mean = 7.500000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
2
Median = 7.500000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
3
Mode = 7.500000
Enter Choice
1.Mean
2.Median
3.Mode
4.Exit
4
Wednesday, March 16, 2011
Base System Conversion BInary--Octa-Decinal-HexaDecimal
Program for Binary, Octal, Hexadecimal Conversions
Program for Binary, Octal, Hexadecimal Conversions
#include
#include
#include
void bd();
void db();
void doc();
void dh();
void od();
void ob();
void bo();
void bh();
void hb();
void hd();
void oh();
void ho();
void main()
{
int n;
char c;
begin:
clrscr();
printf(" ****MAIN MENU****
");
printf("Enter your choise.(1-12)
");
printf("1. Binary to Decimal.
");
printf("2. Decimal to Binary.
");
printf("3. Decimal to Octal.
");
printf("4. Decimal to Hexadecimal.
");
printf("5. Octal to Decimal.
");
printf("6. Octal to Binary.
");
printf("7. Binary to Octal.
");
printf("8. Binary to Hexadecimal.
");
printf("9. Hexadecimal to Binary.
");
printf("10. Hexadecimal to Decimal.
");
printf("11. Octal to Hexadecimal.
");
printf("12. Hexadecimal to Octal.
");
scanf("%d",&n);
if(n<1 || n>12)
printf("Invalid Choise
");
if(n==1)
bd();
else if(n==2)
db();
else if(n==3)
doc();
else if(n==4)
{
long a;
clrscr();
printf("Conversion from Decimal to Hexadecimal
");
printf("Enter the decimal number.
");
scanf("%ld",&a);
dh(a);
}
else if(n==5)
od();
else if(n==6)
ob();
else if(n==7)
bo();
else if(n==8)
bh();
else if(n==9)
hb();
else if(n==10)
hd();
else if(n==11)
{
unsigned long n,i=0,a,p=1,t=0;
clrscr();
printf("Conversion from Octal to Hexadecimal.
");
printf("Enter a Octal number
");
scanf("%ld",&n);
i=0;
while(n!=0)
{
a=n%10;
if(a>7)
t=1;
n=n/10;
i=i+a*p;
p=p*8;
}
if(t==0)
{
printf("Hexadecimal eq=");
oh(i);
}
else if(t==1)
printf("Numbert entered is not octal.
");
}
else if(n==12)
ho();
printf("
Do you Wish to continue(Y/N)
");
scanf("%s",&c);
c=toupper(c);
if(c=='Y')
goto begin;
getch();
}
void bd()
{
int n,b=0,a[6],i=0,t=0;
clrscr();
printf("Conversion from Binary to Decimal
");
printf("Enter Binary Number
");
scanf("%d",&n);
while(n!=0)
{
a[i]=n%10;
n=n/10;
if(a[i]!=1 && a[i]!=0)
t=1;
i++;
}
a[i]=2;
n=1;
for(i=0;a[i]!=2;i++)
{
b=b+a[i]*n;
n=n*2;
}
if(t==0)
printf("Decimal Equivalent=%d",b);
else if(t==1)
printf("Entered number is not binary.");
}
void db()
{
int dec,bin,n,i=0,a[10];
clrscr();
printf("Conversion from Decimal to Binary
");
printf("Input decimal no.");
scanf("%d",&dec);
do
{
a[i]=dec%2;
dec=dec/2;
i++;
}while(dec!=0);
for(n=i-1;n>=0;n--)
printf("%d",a[n]);
}
void doc()
{
int n,i,a[10];
clrscr();
printf("Conversion from Decimal to Octal
");
printf("Enter a Decimal number
");
scanf("%d",&n);
i=0;
printf("Octal equavalent of %d is ",n);
while(n!=0)
{
a[i]=n%8;
n=n/8;
i++;
}
i--;
for(;i>=0;i--)
printf("%d",a[i]);
}
void dh(long n)
{
long i;
if(n>0)
{
i=n%16;
n=n/16;
dh(n);
if(i>=10)
{
switch(i)
{
case 10:
printf("A");
break;
case 11:
printf("B");
break;
case 12:
printf("C");
break;
case 13:
printf("D");
break;
case 14:
printf("E");
break;
case 15:
printf("F");
break;
}
}
else
printf("%ld",i);
}
}
void od()
{
unsigned long n,i=0,a,p=1,t=0;
clrscr();
printf("Conversion from Octal to Decimal
");
printf("Enter a Octal number
");
scanf("%ld",&n);
i=0;
printf("Decimal equavalent of %ld",n);
while(n!=0)
{
a=n%10;
if(a>7)
t=1;
n=n/10;
i=i+a*p;
p=p*8;
}
if(t==0)
printf("= %ld",i);
else if(t==1)
printf(" can't be calculated because it is not an Octal Number.
");
}
void ob()
{
int n,a[6],i=0,t=0;
clrscr();
printf("Convertion from Octal to Binary.
");
printf("Enter an Octal Number.
");
scanf("%d",&n);
while(n!=0)
{
a[i]=n%10;
n=n/10;
if(a[i]>7)
t=1;
i++;
}
i--;
if(t==0)
for(;i>=0;i--)
{
switch(a[i])
{
case 0:
printf("000");
break;
case 1:
printf("001");
break;
case 2:
printf("010");
break;
case 3:
printf("011");
break;
case 4:
printf("100");
break;
case 5:
printf("101");
break;
case 6:
printf("110");
break;
case 7:
printf("111");
break;
}
}
if(t==1)
printf("Not a Octal number
");
}
void bo()
{
int i=0,a[5],t=0;
long int n;
clrscr();
printf("Convertion From Binary to Octal
");
printf("Enter a Binary number
");
scanf("%ld",&n);
while(n!=0)
{
a[i]=n%1000;
n=n/1000;
if(a[i]>111)
t=1;
i++;
}
i--;
if(t==0)
for(;i>=0;i--)
{
switch(a[i])
{
case 0:
printf("0");
break;
case 1:
printf("1");
break;
case 10:
printf("2");
break;
case 11:
printf("3");
break;
case 100:
printf("4");
break;
case 101:
printf("5");
break;
case 110:
printf("6");
break;
case 111:
printf("7");
break;
default:
printf("
Entered number is not binary.
Printed value is not
correct.
");
break;
}
}
if(t==1)
printf("Number is not Binary
");
}
void bh()
{
int i=0,a[5],t=0;
long int n;
clrscr();
printf("Convertion from Binary to Hexadecimal
");
printf("Enter a Binary number
");
scanf("%ld",&n);
while(n!=0)
{
a[i]=n%10000;
n=n/10000;
if(a[i]>1111)
t=1;
i++;
}
i--;
if(t==0)
for(;i>=0;i--)
{
switch(a[i])
{
case 0:
printf("0");
break;
case 1:
printf("1");
break;
case 10:
printf("2");
break;
case 11:
printf("3");
break;
case 100:
printf("4");
break;
case 101:
printf("5");
break;
case 110:
printf("6");
break;
case 111:
printf("7");
break;
case 1000:
printf("8");
break;
case 1001:
printf("9");
break;
case 1010:
printf("A");
break;
case 1011:
printf("B");
break;
case 1100:
printf("C");
break;
case 1101:
printf("D");
break;
case 1110:
printf("E");
break;
case 1111:
printf("F");
break;
default:
printf("
Entered number is not binary.
Printed value is not
correct.
");
break;
}
}
if(t==1)
printf("Number is not Binary
");
}
void hb()
{
int i;
char s[20];
clrscr();
printf("Convertion from Hexadecimal to Binary
");
printf("Enter a Hexadecimal number
");
scanf("%s",s);
//gets(s);
printf("Binary Equivalent=");
for(i=0;s[i]!=NULL;i++)
{
switch(s[i])
{
case '0':
printf("0000");
break;
case '1':
printf("0001");
break;
case '2':
printf("0010");
break;
case '3':
printf("0011");
break;
case '4':
printf("0100");
break;
case '5':
printf("0101");
break;
case '6':
printf("0110");
break;
case '7':
printf("0111");
break;
case '8':
printf("1000");
break;
case '9':
printf("1001");
break;
case 'a':
case 'A':
printf("1010");
break;
case 'b':
case 'B':
printf("1011");
break;
case 'c':
case 'C':
printf("1100");
break;
case 'd':
case 'D':
printf("1101");
break;
case 'e':
case 'E':
printf("1110");
break;
case 'f':
case 'F':
printf("1111");
break;
default:
printf("
Entered number is not Hexadecimal.
Printed value is not
correct.
");
break;
}
}
}
void hd()
{
int i,a[20];
unsigned long int h=0,m=1;
char s[20];
clrscr();
printf("Convertion from Hexadecimal to Decimal
");
printf("Enter a Hexadecimal number
");
scanf("%s",s);
printf("Decimal Equivalent=");
for(i=0;s[i]!=NULL;i++)
{
switch(s[i])
{
case '0':
a[i]=0;
break;
case '1':
a[i]=1;
break;
case '2':
a[i]=2;
break;
case '3':
a[i]=3;
break;
case '4':
a[i]=4;
break;
case '5':
a[i]=5;
break;
case '6':
a[i]=6;
break;
case '7':
a[i]=7;
break;
case '8':
a[i]=8;
break;
case '9':
a[i]=9;
break;
case 'a':
case 'A':
a[i]=10;
break;
case 'b':
case 'B':
a[i]=11;
break;
case 'c':
case 'C':
a[i]=12;
break;
case 'd':
case 'D':
a[i]=13;
break;
case 'e':
case 'E':
a[i]=14;
break;
case 'f':
case 'F':
a[i]=15;
break;
default:
printf("
Entered number is not Hexadecimal.
Printed value is not
correct.
");
break;
}
}
i--;
for(;i>=0;i--)
{
h=h+a[i]*m;
m=m*16;
}
printf("%ld ",h);
}
void oh(long n)
{
long i;
if(n>0)
{
i=n%16;
n=n/16;
oh(n);
if(i>=10)
{
switch(i)
{
case 10:
printf("A");
break;
case 11:
printf("B");
break;
case 12:
printf("C");
break;
case 13:
printf("D");
break;
case 14:
printf("E");
break;
case 15:
printf("F");
break;
}
}
else
printf("%ld",i);
}
}
void ho()
{
int i,a[20];
unsigned long int h=0,m=1;
char s[20];
clrscr();
printf("Convertion from Hexadecimal to Octal
");
printf("Enter a Hexadecimal number
");
scanf("%s",s);
// Converting hex to dec first
for(i=0;s[i]!=NULL;i++)
{
switch(s[i])
{
case '0':
a[i]=0;
break;
case '1':
a[i]=1;
break;
case '2':
a[i]=2;
break;
case '3':
a[i]=3;
break;
case '4':
a[i]=4;
break;
case '5':
a[i]=5;
break;
case '6':
a[i]=6;
break;
case '7':
a[i]=7;
break;
case '8':
a[i]=8;
break;
case '9':
a[i]=9;
break;
case 'a':
case 'A':
a[i]=10;
break;
case 'b':
case 'B':
a[i]=11;
break;
case 'c':
case 'C':
a[i]=12;
break;
case 'd':
case 'D':
a[i]=13;
break;
case 'e':
case 'E':
a[i]=14;
break;
case 'f':
case 'F':
a[i]=15;
break;
default:
printf("
Entered number is not Hexadecimal.
Printed value is not
correct.
");
break;
}
}
i--;
for(;i>=0;i--)
{
h=h+a[i]*m;
m=m*16;
}
// Now convering from decimal to octal (h)
i=0;
printf("Octal equavalent=");
while(h!=0)
{
a[i]=h%8;
h=h/8;
i++;
}
i--;
for(;i>=0;i--)
printf("%d",a[i]);
}
Program for Binary, Octal, Hexadecimal Conversions
#include
#include
#include
void bd();
void db();
void doc();
void dh();
void od();
void ob();
void bo();
void bh();
void hb();
void hd();
void oh();
void ho();
void main()
{
int n;
char c;
begin:
clrscr();
printf(" ****MAIN MENU****
");
printf("Enter your choise.(1-12)
");
printf("1. Binary to Decimal.
");
printf("2. Decimal to Binary.
");
printf("3. Decimal to Octal.
");
printf("4. Decimal to Hexadecimal.
");
printf("5. Octal to Decimal.
");
printf("6. Octal to Binary.
");
printf("7. Binary to Octal.
");
printf("8. Binary to Hexadecimal.
");
printf("9. Hexadecimal to Binary.
");
printf("10. Hexadecimal to Decimal.
");
printf("11. Octal to Hexadecimal.
");
printf("12. Hexadecimal to Octal.
");
scanf("%d",&n);
if(n<1 || n>12)
printf("Invalid Choise
");
if(n==1)
bd();
else if(n==2)
db();
else if(n==3)
doc();
else if(n==4)
{
long a;
clrscr();
printf("Conversion from Decimal to Hexadecimal
");
printf("Enter the decimal number.
");
scanf("%ld",&a);
dh(a);
}
else if(n==5)
od();
else if(n==6)
ob();
else if(n==7)
bo();
else if(n==8)
bh();
else if(n==9)
hb();
else if(n==10)
hd();
else if(n==11)
{
unsigned long n,i=0,a,p=1,t=0;
clrscr();
printf("Conversion from Octal to Hexadecimal.
");
printf("Enter a Octal number
");
scanf("%ld",&n);
i=0;
while(n!=0)
{
a=n%10;
if(a>7)
t=1;
n=n/10;
i=i+a*p;
p=p*8;
}
if(t==0)
{
printf("Hexadecimal eq=");
oh(i);
}
else if(t==1)
printf("Numbert entered is not octal.
");
}
else if(n==12)
ho();
printf("
Do you Wish to continue(Y/N)
");
scanf("%s",&c);
c=toupper(c);
if(c=='Y')
goto begin;
getch();
}
void bd()
{
int n,b=0,a[6],i=0,t=0;
clrscr();
printf("Conversion from Binary to Decimal
");
printf("Enter Binary Number
");
scanf("%d",&n);
while(n!=0)
{
a[i]=n%10;
n=n/10;
if(a[i]!=1 && a[i]!=0)
t=1;
i++;
}
a[i]=2;
n=1;
for(i=0;a[i]!=2;i++)
{
b=b+a[i]*n;
n=n*2;
}
if(t==0)
printf("Decimal Equivalent=%d",b);
else if(t==1)
printf("Entered number is not binary.");
}
void db()
{
int dec,bin,n,i=0,a[10];
clrscr();
printf("Conversion from Decimal to Binary
");
printf("Input decimal no.");
scanf("%d",&dec);
do
{
a[i]=dec%2;
dec=dec/2;
i++;
}while(dec!=0);
for(n=i-1;n>=0;n--)
printf("%d",a[n]);
}
void doc()
{
int n,i,a[10];
clrscr();
printf("Conversion from Decimal to Octal
");
printf("Enter a Decimal number
");
scanf("%d",&n);
i=0;
printf("Octal equavalent of %d is ",n);
while(n!=0)
{
a[i]=n%8;
n=n/8;
i++;
}
i--;
for(;i>=0;i--)
printf("%d",a[i]);
}
void dh(long n)
{
long i;
if(n>0)
{
i=n%16;
n=n/16;
dh(n);
if(i>=10)
{
switch(i)
{
case 10:
printf("A");
break;
case 11:
printf("B");
break;
case 12:
printf("C");
break;
case 13:
printf("D");
break;
case 14:
printf("E");
break;
case 15:
printf("F");
break;
}
}
else
printf("%ld",i);
}
}
void od()
{
unsigned long n,i=0,a,p=1,t=0;
clrscr();
printf("Conversion from Octal to Decimal
");
printf("Enter a Octal number
");
scanf("%ld",&n);
i=0;
printf("Decimal equavalent of %ld",n);
while(n!=0)
{
a=n%10;
if(a>7)
t=1;
n=n/10;
i=i+a*p;
p=p*8;
}
if(t==0)
printf("= %ld",i);
else if(t==1)
printf(" can't be calculated because it is not an Octal Number.
");
}
void ob()
{
int n,a[6],i=0,t=0;
clrscr();
printf("Convertion from Octal to Binary.
");
printf("Enter an Octal Number.
");
scanf("%d",&n);
while(n!=0)
{
a[i]=n%10;
n=n/10;
if(a[i]>7)
t=1;
i++;
}
i--;
if(t==0)
for(;i>=0;i--)
{
switch(a[i])
{
case 0:
printf("000");
break;
case 1:
printf("001");
break;
case 2:
printf("010");
break;
case 3:
printf("011");
break;
case 4:
printf("100");
break;
case 5:
printf("101");
break;
case 6:
printf("110");
break;
case 7:
printf("111");
break;
}
}
if(t==1)
printf("Not a Octal number
");
}
void bo()
{
int i=0,a[5],t=0;
long int n;
clrscr();
printf("Convertion From Binary to Octal
");
printf("Enter a Binary number
");
scanf("%ld",&n);
while(n!=0)
{
a[i]=n%1000;
n=n/1000;
if(a[i]>111)
t=1;
i++;
}
i--;
if(t==0)
for(;i>=0;i--)
{
switch(a[i])
{
case 0:
printf("0");
break;
case 1:
printf("1");
break;
case 10:
printf("2");
break;
case 11:
printf("3");
break;
case 100:
printf("4");
break;
case 101:
printf("5");
break;
case 110:
printf("6");
break;
case 111:
printf("7");
break;
default:
printf("
Entered number is not binary.
Printed value is not
correct.
");
break;
}
}
if(t==1)
printf("Number is not Binary
");
}
void bh()
{
int i=0,a[5],t=0;
long int n;
clrscr();
printf("Convertion from Binary to Hexadecimal
");
printf("Enter a Binary number
");
scanf("%ld",&n);
while(n!=0)
{
a[i]=n%10000;
n=n/10000;
if(a[i]>1111)
t=1;
i++;
}
i--;
if(t==0)
for(;i>=0;i--)
{
switch(a[i])
{
case 0:
printf("0");
break;
case 1:
printf("1");
break;
case 10:
printf("2");
break;
case 11:
printf("3");
break;
case 100:
printf("4");
break;
case 101:
printf("5");
break;
case 110:
printf("6");
break;
case 111:
printf("7");
break;
case 1000:
printf("8");
break;
case 1001:
printf("9");
break;
case 1010:
printf("A");
break;
case 1011:
printf("B");
break;
case 1100:
printf("C");
break;
case 1101:
printf("D");
break;
case 1110:
printf("E");
break;
case 1111:
printf("F");
break;
default:
printf("
Entered number is not binary.
Printed value is not
correct.
");
break;
}
}
if(t==1)
printf("Number is not Binary
");
}
void hb()
{
int i;
char s[20];
clrscr();
printf("Convertion from Hexadecimal to Binary
");
printf("Enter a Hexadecimal number
");
scanf("%s",s);
//gets(s);
printf("Binary Equivalent=");
for(i=0;s[i]!=NULL;i++)
{
switch(s[i])
{
case '0':
printf("0000");
break;
case '1':
printf("0001");
break;
case '2':
printf("0010");
break;
case '3':
printf("0011");
break;
case '4':
printf("0100");
break;
case '5':
printf("0101");
break;
case '6':
printf("0110");
break;
case '7':
printf("0111");
break;
case '8':
printf("1000");
break;
case '9':
printf("1001");
break;
case 'a':
case 'A':
printf("1010");
break;
case 'b':
case 'B':
printf("1011");
break;
case 'c':
case 'C':
printf("1100");
break;
case 'd':
case 'D':
printf("1101");
break;
case 'e':
case 'E':
printf("1110");
break;
case 'f':
case 'F':
printf("1111");
break;
default:
printf("
Entered number is not Hexadecimal.
Printed value is not
correct.
");
break;
}
}
}
void hd()
{
int i,a[20];
unsigned long int h=0,m=1;
char s[20];
clrscr();
printf("Convertion from Hexadecimal to Decimal
");
printf("Enter a Hexadecimal number
");
scanf("%s",s);
printf("Decimal Equivalent=");
for(i=0;s[i]!=NULL;i++)
{
switch(s[i])
{
case '0':
a[i]=0;
break;
case '1':
a[i]=1;
break;
case '2':
a[i]=2;
break;
case '3':
a[i]=3;
break;
case '4':
a[i]=4;
break;
case '5':
a[i]=5;
break;
case '6':
a[i]=6;
break;
case '7':
a[i]=7;
break;
case '8':
a[i]=8;
break;
case '9':
a[i]=9;
break;
case 'a':
case 'A':
a[i]=10;
break;
case 'b':
case 'B':
a[i]=11;
break;
case 'c':
case 'C':
a[i]=12;
break;
case 'd':
case 'D':
a[i]=13;
break;
case 'e':
case 'E':
a[i]=14;
break;
case 'f':
case 'F':
a[i]=15;
break;
default:
printf("
Entered number is not Hexadecimal.
Printed value is not
correct.
");
break;
}
}
i--;
for(;i>=0;i--)
{
h=h+a[i]*m;
m=m*16;
}
printf("%ld ",h);
}
void oh(long n)
{
long i;
if(n>0)
{
i=n%16;
n=n/16;
oh(n);
if(i>=10)
{
switch(i)
{
case 10:
printf("A");
break;
case 11:
printf("B");
break;
case 12:
printf("C");
break;
case 13:
printf("D");
break;
case 14:
printf("E");
break;
case 15:
printf("F");
break;
}
}
else
printf("%ld",i);
}
}
void ho()
{
int i,a[20];
unsigned long int h=0,m=1;
char s[20];
clrscr();
printf("Convertion from Hexadecimal to Octal
");
printf("Enter a Hexadecimal number
");
scanf("%s",s);
// Converting hex to dec first
for(i=0;s[i]!=NULL;i++)
{
switch(s[i])
{
case '0':
a[i]=0;
break;
case '1':
a[i]=1;
break;
case '2':
a[i]=2;
break;
case '3':
a[i]=3;
break;
case '4':
a[i]=4;
break;
case '5':
a[i]=5;
break;
case '6':
a[i]=6;
break;
case '7':
a[i]=7;
break;
case '8':
a[i]=8;
break;
case '9':
a[i]=9;
break;
case 'a':
case 'A':
a[i]=10;
break;
case 'b':
case 'B':
a[i]=11;
break;
case 'c':
case 'C':
a[i]=12;
break;
case 'd':
case 'D':
a[i]=13;
break;
case 'e':
case 'E':
a[i]=14;
break;
case 'f':
case 'F':
a[i]=15;
break;
default:
printf("
Entered number is not Hexadecimal.
Printed value is not
correct.
");
break;
}
}
i--;
for(;i>=0;i--)
{
h=h+a[i]*m;
m=m*16;
}
// Now convering from decimal to octal (h)
i=0;
printf("Octal equavalent=");
while(h!=0)
{
a[i]=h%8;
h=h/8;
i++;
}
i--;
for(;i>=0;i--)
printf("%d",a[i]);
}
Friday, March 4, 2011
WAP fro Generica Swap & Simple Swp of two variable all possible method
Swapping two variables
Swapping two variables refers to mutually exchanging the values of two variables. For Example: If X & Y are two integer variable in C, such that
int X = 5;
int Y = 10;
Than after swapping X should be 10 and Y should be 5. Swapping can be done in variety of ways. We discuss few methods below
Method 1: Using Temporary variable
view sourceprint?
1 /* Let t be a temporary variable */
2 int t = X;
3 X = Y;
4 Y = t;
Above Algorithm looks very light & simple. It indeed is, if X & Y are integers.
What if, we are in C++ and X & Y are Objects of user defined class. Creating a temporary variable means constructor and Destructor will be called. Also there are two assignments (the first statement is initialization and not assignment), so Overloaded assignment operator will be called twice. This is a huge amount of task, especially when the Class is heavy.
What if the class has nested objects of another class, which are constructed in the Construction and destroyed in the destructor? Also to further complicate, let us consider the Class inheritance hierarchy, So Constructors of all the Base classes will be called.
But this method may be the only way to swap two objects in many cases.
So, as Himesh Reshammiya says “It’s complicated” !
Method 2: Using XOR operator.
view sourceprint?
1 // Swaping using XOR
2 X = X ^ Y;
3 Y = X ^ Y;
4 X = X ^ Y;
This method does not use the temporary object and use bit-wise operator which is believed to be more compact than other operators (Compiler dependent).
The disadvantage of this method is that it can only be applied to low-level data types like integers & characters (char, short, int, long). C & C++ does not allow bit-wise operation on non-integral operands.
A Major flaw in this algo is that it won’t work if X & Y uses same memory location. The contents of that location will be Zero when the first statement is executed.
view sourceprint?
1 void swap(int *x, int * y){
2 // this check is compulsory, else it may not work properly for cases
3 // where x & y points to the same memory location.
4 if(x != y)
5 x ^= y ^= x ^=y;
6 }
Same Problem will occur if x & y are references to the same memory location.
Method 3: Using +,- operator.
view sourceprint?
1 X = X + Y;
2 Y = X - Y;
3 X = X - Y;
this method can however, only be applied on numeric values.
If we have addition and subtraction overloaded for a user defined type and we accidently try to swap using the above code, then we may run into bigger problems, because the compiler will not complain and the result may not be what we expect it to be.
The issue of arithmetic overflow is also there. For Example: Consider a hypothetical environment where the maximum limit of integers is 100, and we want to swap X & Y with values 40 & 70 respectively. Swapping them using temporary variable (Method 1) or XOR (Method 2) will be correct but in this case the result will be undefined because 40 + 70 = 110 will result in an integer value overflow.
Note: In most of the environments, integers are stored in 2′s complement notation. If we perform above addition and subtraction in 2′s complement notions, then the result will be correct. But that is only because of the cyclic nature of 2′s complement representation and it is not guaranteed by the language.
Method 4: Using *, / operators
The above (Method 3) can be used with multiplication & divide operators in place of +, – operators.
Method 5: Swapping Pointers
Swapping pointers pointing to two different memory locations is very different from swapping the contents of those memory locations, though the results, in some cases, may be similar (not same).
For Example: If you want to swap two variables on heap and only one pointer points to each memory location, swapping the pointers will look similar to swapping the contents of the two memory locations.
Let ptr1 & ptr2 are two integer pointers pointing to memory locations containing 50 & 70 respectively,
then after swapping ptr1 and ptr2 will result in the below memory snap-shot:
Please note that if there is a third pointer ptr3 which also points to memory containing 50, then value-at ptr3 (*ptr3) will not change. But if we swap the contents of memory locations then *ptr3 will also be 70.
Either swapping of pointers or swapping the actual contents of the memory should be done depends on the requirements.
Since pointer variables are of fixed size and are non-negative integers, the XOR method of swapping can be used to swap two pointers.
If we swap the contents and not the pointers then we may end up using method 1 (particularly if we are dealing with user defined classes). And as discussed above it will have the complications of object creation, destruction & assignment operator calling.
Method 6: Generic Swapping
Using generic pointers or Macros in C language (void*) or templates in C++, we can define a generic swap function, which can swap two variable of any given datatype. (The macros may be error prone, though):
Generic pointers
view sourceprint?
1 void swap(void *vp1, void *vp2, int size)
2 {
3 char buffer[large]; // Large is a constant
4 memcpy(buffer,vp1,size);
5 memcpy(vp1,vp2,size);
6 memcpy(vp2,buffer,size);
7 }
Macro
view sourceprint?
1 #define SWAP(x, y, data_type) {data_type t=x; x=y; y=t; }
But the above macro does not work for all types and is more error prone than the other two variations.
Templates
view sourceprint?
1 template void swap(T&a, T &b)
2 {
3 T temp;
4
5 temp = a;
6 a = b;
7 b = temp;
8 }
In the above case the variables are passed by reference so that the actual arguments will get swapped. By default the values are passed by values and hence will swap the local variables of a function. To call the above template function for integers ,
swap(a,b);
Swapping two variables refers to mutually exchanging the values of two variables. For Example: If X & Y are two integer variable in C, such that
int X = 5;
int Y = 10;
Than after swapping X should be 10 and Y should be 5. Swapping can be done in variety of ways. We discuss few methods below
Method 1: Using Temporary variable
view sourceprint?
1 /* Let t be a temporary variable */
2 int t = X;
3 X = Y;
4 Y = t;
Above Algorithm looks very light & simple. It indeed is, if X & Y are integers.
What if, we are in C++ and X & Y are Objects of user defined class. Creating a temporary variable means constructor and Destructor will be called. Also there are two assignments (the first statement is initialization and not assignment), so Overloaded assignment operator will be called twice. This is a huge amount of task, especially when the Class is heavy.
What if the class has nested objects of another class, which are constructed in the Construction and destroyed in the destructor? Also to further complicate, let us consider the Class inheritance hierarchy, So Constructors of all the Base classes will be called.
But this method may be the only way to swap two objects in many cases.
So, as Himesh Reshammiya says “It’s complicated” !
Method 2: Using XOR operator.
view sourceprint?
1 // Swaping using XOR
2 X = X ^ Y;
3 Y = X ^ Y;
4 X = X ^ Y;
This method does not use the temporary object and use bit-wise operator which is believed to be more compact than other operators (Compiler dependent).
The disadvantage of this method is that it can only be applied to low-level data types like integers & characters (char, short, int, long). C & C++ does not allow bit-wise operation on non-integral operands.
A Major flaw in this algo is that it won’t work if X & Y uses same memory location. The contents of that location will be Zero when the first statement is executed.
view sourceprint?
1 void swap(int *x, int * y){
2 // this check is compulsory, else it may not work properly for cases
3 // where x & y points to the same memory location.
4 if(x != y)
5 x ^= y ^= x ^=y;
6 }
Same Problem will occur if x & y are references to the same memory location.
Method 3: Using +,- operator.
view sourceprint?
1 X = X + Y;
2 Y = X - Y;
3 X = X - Y;
this method can however, only be applied on numeric values.
If we have addition and subtraction overloaded for a user defined type and we accidently try to swap using the above code, then we may run into bigger problems, because the compiler will not complain and the result may not be what we expect it to be.
The issue of arithmetic overflow is also there. For Example: Consider a hypothetical environment where the maximum limit of integers is 100, and we want to swap X & Y with values 40 & 70 respectively. Swapping them using temporary variable (Method 1) or XOR (Method 2) will be correct but in this case the result will be undefined because 40 + 70 = 110 will result in an integer value overflow.
Note: In most of the environments, integers are stored in 2′s complement notation. If we perform above addition and subtraction in 2′s complement notions, then the result will be correct. But that is only because of the cyclic nature of 2′s complement representation and it is not guaranteed by the language.
Method 4: Using *, / operators
The above (Method 3) can be used with multiplication & divide operators in place of +, – operators.
Method 5: Swapping Pointers
Swapping pointers pointing to two different memory locations is very different from swapping the contents of those memory locations, though the results, in some cases, may be similar (not same).
For Example: If you want to swap two variables on heap and only one pointer points to each memory location, swapping the pointers will look similar to swapping the contents of the two memory locations.
Let ptr1 & ptr2 are two integer pointers pointing to memory locations containing 50 & 70 respectively,
then after swapping ptr1 and ptr2 will result in the below memory snap-shot:
Please note that if there is a third pointer ptr3 which also points to memory containing 50, then value-at ptr3 (*ptr3) will not change. But if we swap the contents of memory locations then *ptr3 will also be 70.
Either swapping of pointers or swapping the actual contents of the memory should be done depends on the requirements.
Since pointer variables are of fixed size and are non-negative integers, the XOR method of swapping can be used to swap two pointers.
If we swap the contents and not the pointers then we may end up using method 1 (particularly if we are dealing with user defined classes). And as discussed above it will have the complications of object creation, destruction & assignment operator calling.
Method 6: Generic Swapping
Using generic pointers or Macros in C language (void*) or templates in C++, we can define a generic swap function, which can swap two variable of any given datatype. (The macros may be error prone, though):
Generic pointers
view sourceprint?
1 void swap(void *vp1, void *vp2, int size)
2 {
3 char buffer[large]; // Large is a constant
4 memcpy(buffer,vp1,size);
5 memcpy(vp1,vp2,size);
6 memcpy(vp2,buffer,size);
7 }
Macro
view sourceprint?
1 #define SWAP(x, y, data_type) {data_type t=x; x=y; y=t; }
But the above macro does not work for all types and is more error prone than the other two variations.
Templates
view sourceprint?
1 template
2 {
3 T temp;
4
5 temp = a;
6 a = b;
7 b = temp;
8 }
In the above case the variables are passed by reference so that the actual arguments will get swapped. By default the values are passed by values and hence will swap the local variables of a function. To call the above template function for integers ,
swap
Saturday, February 26, 2011
Prime Number Generation Using Sieve of Eratosthenes
public class prime_sieve
{
public static void main(String a[])
{
runEratosthenesSieve(100);
}
public static void runEratosthenesSieve(int upperBound) {
int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
boolean[] isComposite = new boolean[upperBound + 1];
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
System.out.print(m + " ");
for (int k = m * m; k <= upperBound; k += m)
isComposite[k] = true;
}
}
for (int m = upperBoundSquareRoot; m <= upperBound; m++)
if (!isComposite[m])
System.out.print(m + " ");
}
}
{
public static void main(String a[])
{
runEratosthenesSieve(100);
}
public static void runEratosthenesSieve(int upperBound) {
int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
boolean[] isComposite = new boolean[upperBound + 1];
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
System.out.print(m + " ");
for (int k = m * m; k <= upperBound; k += m)
isComposite[k] = true;
}
}
for (int m = upperBoundSquareRoot; m <= upperBound; m++)
if (!isComposite[m])
System.out.print(m + " ");
}
}
Subscribe to:
Posts
(
Atom
)
