Your browser is not supported. Please, update your browser or switch to a different one. Learn more about which browsers are supported.
Task description
A non-empty array A consisting of N numbers is given. The array is sorted in non-decreasing order. The absolute distinct count of this array is the number of distinct absolute values among the elements of the array.
For example, consider array A such that:
A[0] = -5 A[1] = -3 A[2] = -1 A[3] = 0 A[4] = 3 A[5] = 6The absolute distinct count of this array is 5, because there are 5 distinct absolute values among the elements of this array, namely 0, 1, 3, 5 and 6.
Write a function:
def solution(A)
that, given a non-empty array A consisting of N numbers, returns absolute distinct count of array A.
For example, given array A such that:
A[0] = -5 A[1] = -3 A[2] = -1 A[3] = 0 A[4] = 3 A[5] = 6the function should return 5, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647];
- array A is sorted in non-decreasing order.
Task timeline
[-32340, -32198, -32188, -32122, -31417, -30830, -29556, -29241, -29068, -26202, -25640, -23737, -23660, -23436, -22643, -22550, -22173, -20585, -20366, -19151, -18370, -18336, -18039, -17858, -17548, -17377, -17089, -16083, -15737, -15668, -15419, -15122, -14845, -14156, -14026, -13816, -13466, -12876, -11760, -11407, -11036, -8703, -8019, -6520, -6081, -5986, -5171, -5135, -4946, -4342, -1581, -264, 111, 303, 2191, 3058, 3738, 4017, 4563, 5281, 5642, 6309, 7132, 7255, 7289, 7379, 7970, 8312, 8617, 9050, 9064, 9459, 10581, 10592, 11164, 13054, 13388, 14041, 16373, 16765, 17933, 18946, 19335, 19487, 20073, 23500, 23840, 24182, 24333, 24591, 24650, 25590, 25944, 28134, 28362, 28376, 29799, 30151, 30488, 32637]
[-32, -31, -30, -27, -26, -24, -23, -21, -18, -17, -16, -14, -13, -11, -10, -9, -8, -7, -6, -5, -4, -3, -1, 0, 1, 2, 4, 5, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
function result: 100
function result: 32
function result: 26
[-32340, -32198, -32188, -32122, -31417, -30830, -29556, -29241, -29068, -26202, -25640, -23737, -23660, -23436, -22643, -22550, -22173, -20585, -20366, -19151, -18370, -18336, -18039, -17858, -17548, -17377, -17089, -16083, -15737, -15668, -15419, -15122, -14845, -14156, -14026, -13816, -13466, -12876, -11760, -11407, -11036, -8703, -8019, -6520, -6081, -5986, -5171, -5135, -4946, -4342, -1581, -264, 111, 303, 2191, 3058, 3738, 4017, 4563, 5281, 5642, 6309, 7132, 7255, 7289, 7379, 7970, 8312, 8617, 9050, 9064, 9459, 10581, 10592, 11164, 13054, 13388, 14041, 16373, 16765, 17933, 18946, 19335, 19487, 20073, 23500, 23840, 24182, 24333, 24591, 24650, 25590, 25944, 28134, 28362, 28376, 29799, 30151, 30488, 32637]
[-32, -31, -30, -27, -26, -24, -23, -21, -18, -17, -16, -14, -13, -11, -10, -9, -8, -7, -6, -5, -4, -3, -1, 0, 1, 2, 4, 5, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
[-32, -32, -31, -29, -28, -26, -24, -24, -23, -22, -17, -17, -17, -16, -15, -15, -8, -8, -7, -6, -5, -4, -4, -3, -3, -3, -2, -1, 2, 4, 5, 7, 10, 11, 13, 16, 16, 16, 16, 17, 18, 19, 21, 22, 22, 23, 25, 28, 28, 29]
function result: 100
function result: 32
function result: 26
[-32340, -32198, -32188, -32122, -31417, -30830, -29556, -29241, -29068, -26202, -25640, -23737, -23660, -23436, -22643, -22550, -22173, -20585, -20366, -19151, -18370, -18336, -18039, -17858, -17548, -17377, -17089, -16083, -15737, -15668, -15419, -15122, -14845, -14156, -14026, -13816, -13466, -12876, -11760, -11407, -11036, -8703, -8019, -6520, -6081, -5986, -5171, -5135, -4946, -4342, -1581, -264, 111, 303, 2191, 3058, 3738, 4017, 4563, 5281, 5642, 6309, 7132, 7255, 7289, 7379, 7970, 8312, 8617, 9050, 9064, 9459, 10581, 10592, 11164, 13054, 13388, 14041, 16373, 16765, 17933, 18946, 19335, 19487, 20073, 23500, 23840, 24182, 24333, 24591, 24650, 25590, 25944, 28134, 28362, 28376, 29799, 30151, 30488, 32637]
[-32, -31, -30, -27, -26, -24, -23, -21, -18, -17, -16, -14, -13, -11, -10, -9, -8, -7, -6, -5, -4, -3, -1, 0, 1, 2, 4, 5, 7, 8, 10, 11, 12, 13, 14, 15, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
[-32, -32, -31, -29, -28, -26, -24, -24, -23, -22, -17, -17, -17, -16, -15, -15, -8, -8, -7, -6, -5, -4, -4, -3, -3, -3, -2, -1, 2, 4, 5, 7, 10, 11, 13, 16, 16, 16, 16, 17, 18, 19, 21, 22, 22, 23, 25, 28, 28, 29]
The solution obtained perfect score.