We draw N discs on a plane. The discs are numbered from 0 to N − 1. An array A of N non-negative integers, specifying the radiuses of the discs, is given. The J-th disc is drawn with its center at (J, 0) and radius A[J].
We say that the J-th disc and K-th disc intersect if J ≠ K and the J-th and K-th discs have at least one common point (assuming that the discs contain their borders).
The figure below shows discs drawn for N = 6 and A as follows:
A[0] = 1 A[1] = 5 A[2] = 2 A[3] = 1 A[4] = 4 A[5] = 0There are eleven (unordered) pairs of discs that intersect, namely:
- discs 1 and 4 intersect, and both intersect with all the other discs;
- disc 2 also intersects with discs 0 and 3.
Write a function:
fun solution(A: IntArray): Int
that, given an array A describing N discs as explained above, returns the number of (unordered) pairs of intersecting discs. The function should return −1 if the number of intersecting pairs exceeds 10,000,000.
Given array A shown above, the function should return 11, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..100,000];
- each element of array A is an integer within the range [0..2,147,483,647].
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
}
private fun calculateXRange(x: Int, r: Int): LongRange {
val minX = x - r.toLong()
val maxX = x + r.toLong()
return LongRange(minX, maxX)
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
val MAX_PAIRS_ALLOWED = 10_000_000L
//calculate startX and endX for each disc
//as y is always 0 so we don't care about it. We only need X
val ranges = Array(A.size) { i ->
calculateXRange(i, A[i])
}
//sort Xranges by the startX
ranges.sortBy { range ->
range.start
}
val starts = Array(ranges.size) {index ->
ranges[index].start
}
var count = 0
for (i in 0 until ranges.size) {
val checkRange = ranges[i]
//find the right most disc whose start is less than or equal to end of current disc
val index = bisectRight(starts, checkRange.endInclusive, i)
//the number of discs covered by this disc are:
//count(the next disc/range ... to the last disc/range covered by given disc/range)
//example: given disc index = 3, last covered (by given disc) disc index = 5
//count = 5 - 3 = 2
//because there are only 2 discs covered by given disc
// (immediate next disc with index 4 and last covered disc at index 5)
val intersections = (index - i)
//because we are only considering discs intersecting/covered by a given disc to the right side
//and ignore any discs that are intersecting on left (because previous discs have already counted those
// when checking for their right intersects) so this calculation avoids any duplications
count += intersections
if (count > MAX_PAIRS_ALLOWED) {
return -1
}
}
return if (count > MAX_PAIRS_ALLOWED) {
-1
} else {
count
}
}
private fun calculateXRange(x: Int, r: Int): LongRange {
val minX = x - r.toLong()
val maxX = x + r.toLong()
return LongRange(minX, maxX)
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
val MAX_PAIRS_ALLOWED = 10_000_000L
//calculate startX and endX for each disc
//as y is always 0 so we don't care about it. We only need X
val ranges = Array(A.size) { i ->
calculateXRange(i, A[i])
}
//sort Xranges by the startX
ranges.sortBy { range ->
range.start
}
val starts = Array(ranges.size) {index ->
ranges[index].start
}
var count = 0
for (i in 0 until ranges.size) {
val checkRange = ranges[i]
//find the right most disc whose start is less than or equal to end of current disc
val index = bisectRight(starts, checkRange.endInclusive, i)
//the number of discs covered by this disc are:
//count(the next disc/range ... to the last disc/range covered by given disc/range)
//example: given disc index = 3, last covered (by given disc) disc index = 5
//count = 5 - 3 = 2
//because there are only 2 discs covered by given disc
// (immediate next disc with index 4 and last covered disc at index 5)
val intersections = (index - i)
//because we are only considering discs intersecting/covered by a given disc to the right side
//and ignore any discs that are intersecting on left (because previous discs have already counted those
// when checking for their right intersects) so this calculation avoids any duplications
count += intersections
if (count > MAX_PAIRS_ALLOWED) {
return -1
}
}
return if (count > MAX_PAIRS_ALLOWED) {
-1
} else {
count
}
}
private fun calculateXRange(x: Int, r: Int): LongRange {
val minX = x - r.toLong()
val maxX = x + r.toLong()
return LongRange(minX, maxX)
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
val MAX_PAIRS_ALLOWED = 10_000_000L
//calculate startX and endX for each disc
//as y is always 0 so we don't care about it. We only need X
val ranges = Array(A.size) { i ->
calculateXRange(i, A[i])
}
//sort Xranges by the startX
ranges.sortBy { range ->
range.start
}
val starts = Array(ranges.size) {index ->
ranges[index].start
}
var count = 0
for (i in 0 until ranges.size) {
val checkRange = ranges[i]
//find the right most disc whose start is less than or equal to end of current disc
val index = bisectRight(starts, checkRange.endInclusive, i)
//the number of discs covered by this disc are:
//count(the next disc/range ... to the last disc/range covered by given disc/range)
//example: given disc index = 3, last covered (by given disc) disc index = 5
//count = 5 - 3 = 2
//because there are only 2 discs covered by given disc
// (immediate next disc with index 4 and last covered disc at index 5)
val intersections = (index - i)
//because we are only considering discs intersecting/covered by a given disc to the right side
//and ignore any discs that are intersecting on left (because previous discs have already counted those
// when checking for their right intersects) so this calculation avoids any duplications
count += intersections
if (count > MAX_PAIRS_ALLOWED) {
return -1
}
}
return if (count > MAX_PAIRS_ALLOWED) {
-1
} else {
count
}
}
private fun calculateXRange(x: Int, r: Int): LongRange {
val minX = x - r.toLong()
val maxX = x + r.toLong()
return LongRange(minX, maxX)
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
val MAX_PAIRS_ALLOWED = 10_000_000L
//calculate startX and endX for each disc
//as y is always 0 so we don't care about it. We only need X
val ranges = Array(A.size) { i ->
calculateXRange(i, A[i])
}
//sort Xranges by the startX
ranges.sortBy { range ->
range.start
}
val starts = Array(ranges.size) {index ->
ranges[index].start
}
var count = 0
for (i in 0 until ranges.size) {
val checkRange = ranges[i]
//find the right most disc whose start is less than or equal to end of current disc
val index = bisectRight(starts, checkRange.endInclusive, i)
//the number of discs covered by this disc are:
//count(the next disc/range ... to the last disc/range covered by given disc/range)
//example: given disc index = 3, last covered (by given disc) disc index = 5
//count = 5 - 3 = 2
//because there are only 2 discs covered by given disc
// (immediate next disc with index 4 and last covered disc at index 5)
val intersections = (index - i)
//because we are only considering discs intersecting/covered by a given disc to the right side
//and ignore any discs that are intersecting on left (because previous discs have already counted those
// when checking for their right intersects) so this calculation avoids any duplications
count += intersections
if (count > MAX_PAIRS_ALLOWED) {
return -1
}
}
return if (count > MAX_PAIRS_ALLOWED) {
-1
} else {
count
}
}
private fun calculateXRange(x: Int, r: Int): LongRange {
val minX = x - r.toLong()
val maxX = x + r.toLong()
return LongRange(minX, maxX)
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
// you can also use imports, for example:
// import kotlin.math.*
// you can write to stdout for debugging purposes, e.g.
// println("this is a debug message")
fun solution(A: IntArray): Int {
// write your code in Kotlin
val MAX_PAIRS_ALLOWED = 10_000_000L
//calculate startX and endX for each disc
//as y is always 0 so we don't care about it. We only need X
val ranges = Array(A.size) { i ->
calculateXRange(i, A[i])
}
//sort Xranges by the startX
ranges.sortBy { range ->
range.start
}
val starts = Array(ranges.size) {index ->
ranges[index].start
}
var count = 0
for (i in 0 until ranges.size) {
val checkRange = ranges[i]
//find the right most disc whose start is less than or equal to end of current disc
val index = bisectRight(starts, checkRange.endInclusive, i)
//the number of discs covered by this disc are:
//count(the next disc/range ... to the last disc/range covered by given disc/range)
//example: given disc index = 3, last covered (by given disc) disc index = 5
//count = 5 - 3 = 2
//because there are only 2 discs covered by given disc
// (immediate next disc with index 4 and last covered disc at index 5)
val intersections = (index - i)
//because we are only considering discs intersecting/covered by a given disc to the right side
//and ignore any discs that are intersecting on left (because previous discs have already counted those
// when checking for their right intersects) so this calculation avoids any duplications
count += intersections
if (count > MAX_PAIRS_ALLOWED) {
return -1
}
}
return if (count > MAX_PAIRS_ALLOWED) {
-1
} else {
count
}
}
private fun calculateXRange(x: Int, r: Int): LongRange {
val minX = x - r.toLong()
val maxX = x + r.toLong()
return LongRange(minX, maxX)
}
fun bisectRight(array: Array<Long>, key: Long, arrayStart: Int = 0): Int {
var start = arrayStart
var end = array.size - 1
var bisect = start
while (start <= end) {
val mid = Math.ceil((start + end) / 2.0).toInt()
val midValue = array[mid]
val indexAfterMid = mid + 1
if (key >= midValue) {
bisect = mid
}
if (key >= midValue && (indexAfterMid > end || key < array[indexAfterMid])) {
break
} else if (key < midValue) {
end = mid - 1
} else {
start = mid + 1
}
}
return bisect
}
The solution obtained perfect score.