amustea
BAN USERTwo circles intersecting means the distance between their centers being less (or equal) to the sum of their radiuses.
Here's the O(n*n) solution, which does not require any additional memory:
public static void main(String[] args) {
int[] xCoord = new int[]{0,2,1};
int[] yCoord = new int[]{0,4,1};
int[] radius = new int[]{0,1,2};
for(int i = 0;i<2;i++)
{
for(int j=i+1;j<3;j++)
{
double cathX = Math.abs(xCoord[j] - xCoord[i]);
double cathY = Math.abs(yCoord[j] - yCoord[i]);
if(Math.sqrt(Math.pow(cathX, 2) + Math.pow(cathY, 2) ) <= radius[i] + radius[j] )
{
System.out.println(" circles " + (int)(i+1) + " and " + (int)(j+1) + " intersect");
}
}
}
}
The O(nlogn) solution will involve 2 iterations, one per each axis, as follows:
1. Modify all 3 arrays such that array X is sorted (sorting will take O(nlogn)). Compare all adjacent circles and check for overlap.
2. Repeat the same step such that array Y is sorted.
You can use a hash to store each char. If a char is already in the hash, it contains a duplicate.
If you are allowed to modify the string you can sort it and then search for two adjacent characters being the same char.
For part B - what do you mean by 20 chars? Length of string is not greater than 20 or there are 20 different letters in the string? You can use an array of size 20 or an int (right-most 20 bits of it to be more precise).
Code to follow :)
I thought the question was asking for multiplication with ALL numbers 2..6.
Yes, such number exists.
142857 (1428570, 14285700, 142857000) is a good example, anyone can share a way to logically find such numbers (like a rule with pen and paper).
here are some more:
142857
142857 x 2 = 285714
142857 x 3 = 428571
142857 x 4 = 571428
142857 x 5 = 714285
142857 x 6 = 857142
1428570
1428570 x 2 = 2857140
1428570 x 3 = 4285710
1428570 x 4 = 5714280
1428570 x 5 = 7142850
1428570 x 6 = 8571420
1429857
1429857 x 2 = 2859714
1429857 x 3 = 4289571
1429857 x 4 = 5719428
1429857 x 5 = 7149285
1429857 x 6 = 8579142
14285700
14285700 x 2 = 28571400
14285700 x 3 = 42857100
14285700 x 4 = 57142800
14285700 x 5 = 71428500
14285700 x 6 = 85714200
14298570
14298570 x 2 = 28597140
14298570 x 3 = 42895710
14298570 x 4 = 57194280
14298570 x 5 = 71492850
14298570 x 6 = 85791420
14299857
14299857 x 2 = 28599714
14299857 x 3 = 42899571
14299857 x 4 = 57199428
14299857 x 5 = 71499285
14299857 x 6 = 85799142
142857000
142857000 x 2 = 285714000
142857000 x 3 = 428571000
142857000 x 4 = 571428000
142857000 x 5 = 714285000
142857000 x 6 = 857142000
142985700
142985700 x 2 = 285971400
142985700 x 3 = 428957100
142985700 x 4 = 571942800
142985700 x 5 = 714928500
142985700 x 6 = 857914200
142998570
142998570 x 2 = 285997140
142998570 x 3 = 428995710
142998570 x 4 = 571994280
142998570 x 5 = 714992850
142998570 x 6 = 857991420
142999857
142999857 x 2 = 285999714
142999857 x 3 = 428999571
142999857 x 4 = 571999428
142999857 x 5 = 714999285
142999857 x 6 = 857999142
1428570000
1428570000 x 2 = 2857140000
1428570000 x 3 = 4285710000
1428570000 x 4 = 5714280000
1428570000 x 5 = 7142850000
1428570000 x 6 = 8571420000
1429857000
1429857000 x 2 = 2859714000
1429857000 x 3 = 4289571000
1429857000 x 4 = 5719428000
1429857000 x 5 = 7149285000
1429857000 x 6 = 8579142000
1429985700
1429985700 x 2 = 2859971400
1429985700 x 3 = 4289957100
1429985700 x 4 = 5719942800
1429985700 x 5 = 7149928500
1429985700 x 6 = 8579914200
1429998570
1429998570 x 2 = 2859997140
1429998570 x 3 = 4289995710
1429998570 x 4 = 5719994280
1429998570 x 5 = 7149992850
1429998570 x 6 = 8579991420
1429999857
1429999857 x 2 = 2859999714
1429999857 x 3 = 4289999571
1429999857 x 4 = 5719999428
1429999857 x 5 = 7149999285
1429999857 x 6 = 8579999142
Looks like 142xxxx857 is a pattern, where xxxx can be any number of 9 (digit 9).
If their areas intersect, this means the circles themselves intersect as well.
- amustea August 28, 2012