Codility Number of Disc intersections
Vložit
- čas přidán 6. 09. 2024
- My solution to Codility Number of Disc intersections. This is the third task in the sorting lesson.
NumberOfDiscIntersections is a respectable exercise in the sorting lesson on Codility. The goal is to find the number of intersections between discs that are specified in an array. The index of the array represents the position of the disc on the x-axis and the value in the array represents the disc's radius.
This video shows my Java solution that scores 100% on Codility.
The best explanation on the internet.
Thanks!
Your solution is great. thanks Dave.
Thanks for saying so and for watching.
Hi Dave, your videos are great! Keep it on
Thanks Matias!
Great video, thanks for this comprehensive explanation :)
Thanks Bipesh.
I can't understand clear how we create the array in minute 6 .. can you signefecent the strategy more please ?
and thank a lot ☺️
Hi. This array is how many discs have started at this point on the X-axis (eg. the left edge of the disc covers this point or is further to the left of this point). So, at position 0, 4 discs have started (the discs with centre positions 0, 1, 2 and 4). At the next position, no new disc starts, so the value is still 4. Then at the next position, disc with 3 at the centre starts, so now we add this to the 4 to get 5. It carries on like this. I hope this makes sense.
Hey Dave here is my Solution kind regards!!
public int discIntersections(int[] a) {
int[] start = new int[a.length]; int[] end = new int[a.length];
for (int i = 0; i < a.length; i++) {
// get start and end of circle
start[i] = i - a[i];end[i] = i + a[i];
}
int count = 0;
for (int i = 0; i < a.length; i++) {
int s = start[i];
int e = end[i];
for (int j = i + 1; j< a.length ; j++) {
//First condition if a circle contain a circle e.q circle 2(-4,6) contain circle 0 (-1,+1)
//Second condition e.g c0 (-1,1) c2 (0,2) 1>0>-1
//Third condition r.g c0(-1,1) c2(0,2) but if we check from left
if ((start[j] = e) |(start[j]>=s && start[j] =s && end[j]
Great, a bit shorter than my solution. Did you try it in Codility?
@@javadave Hi, no i do not try in Codility
@@Mahmoud-xe8hz this is good but time complexity is NxN
Hi, Dave.
I don't get it about max(4,4) -1, max(4, 6) - 1.... since 6:47. I cannot catch your mind. Did I miss anything?
Hi Terrence... this one was one of my favourite problems and very trickey. By max(4,4) I mean just the maximum number between 4 and 4 (4 in this case).... Max(4,6)=6, etc. I hope that makes sense.
Hello Dave
Hello
I will be honest with you, I've gotten lost to understand the task :(
Yes, this one confused me quite a bit. That's why there's a break in the video when I work it out.