I will be generating two random numbers one after the another using the Random class in Java between 0 and a given number x.My aim is to fill an array of length x+1 using these numbers and calculate the following:
Magnitude:The maximum difference between two numbers.
degree:The number of random number generations, required before the array gets filled.Note that two numbers generated consecutively add 1 to the degree.
degree_of_intersection:The number of times the interval between 2 generated numbers overlapped with some interval of previously generated 2 numbers.
I calculated this using the following code in Java and for simplicity i have assumed x=9.
class Randm
{
public static void main(String []args)
{
int a,count=0,r_no1,r_no2,l,r;
Random rd=new Random();
int magnitude=0,degree=0,degree_of_intersection=0;
int []jump=new int[10];
for(int i=0;i<10;++i)
{
jump[i]=0;
}
while(count!=10)
{
++degree;
r_no1=rd.nextInt(10);
r_no2=rd.nextInt(10);
if(Math.abs(r_no1-r_no2)>magnitude)
magnitude=Math.abs(r_no1-r_no2);
if(r_no1<r_no2)
{l=r_no1;r=r_no2;}
else {r=r_no1;l=r_no2;}
for(int i=l;i<=r;++i)
{
if(jump[i]!=0)
{
++degree_of_intersection;
i=jump[i];
continue;
}
else
{
jump[i]=r;
++count;
/*FILL THE ARRAY AT INDEX i*/
}
}
}
System.out.println("\nthe magnitude and degree of randomness is "+magnitude+" and "+degree);
System.out.println("\nthe degree of intersection is "+degree_of_intersection);
}
}
The problem is that because i have used an array jump of length x+1 that helps me to calculate degree_of intersection easily, my space complexity is LINEAR
Whereas, I have to achieve constant space complexity.
Kindly note that besides the array to fill all other data structures used will be counted in space complexity.
Aucun commentaire:
Enregistrer un commentaire