30
\$\begingroup\$

The task

Given any array of integers, e.g.:

[-1,476,578,27,0,1,-1,1,2]

and an index of that array (this example uses 0 based indexing, though you can use 1 based indexing as well.):

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]

Then return the nearest number greater than the element at that index. In the example, the closest number greater than 1 is 27 (at 2 indices away).

         index = 5
                 v
[-1,476,578,27,0,1,-1,1,2]
            ^
Nearest greater number

Output = 27

Assumptions

  • Nearest does not include wrapping.
  • The program will never be given an array of length 1 (e.g; [55]).
  • You are to assume there is always a number greater than the given element.
  • If there are 2 numbers greater than the element at equal distances, you can return either one.

I/O pairs

Input:
Index = 45
Array = [69, 43, 89, 93, 62, 25, 4, 11, 115, 87, 174, 60, 84, 58, 28, 67, 71, 157, 47, 8, 33, 192, 187, 87, 175, 32, 135, 25, 137, 92, 183, 151, 147, 7, 133, 7, 41, 12, 96, 147, 9, 134, 197, 3, 107, 164, 90, 199, 21, 71, 77, 62, 190, 122, 33, 127, 185, 58, 92, 106, 26, 24, 56, 79, 71, 24, 24, 114, 17, 84, 121, 188, 6, 177, 114, 159, 159, 102, 50, 136, 47, 32, 1, 199, 74, 141, 125, 23, 118, 9, 12, 100, 94, 166, 12, 9, 179, 147, 149, 178, 90, 71, 141, 49, 74, 100, 199, 160, 120, 14, 195, 112, 176, 164, 68, 88, 108, 72, 124, 173, 155, 146, 193, 30, 2, 186, 102, 45, 147, 99, 178, 84, 83, 93, 153, 11, 171, 186, 157, 32, 90, 57, 181, 5, 157, 106, 20, 5, 194, 130, 100, 97, 3, 87, 116, 57, 125, 157, 190, 83, 148, 90, 44, 156, 167, 131, 100, 58, 139, 183, 53, 91, 151, 65, 121, 61, 40, 80, 40, 68, 73, 20, 135, 197, 124, 190, 108, 66, 21, 27, 147, 118, 192, 29, 193, 27, 155, 93, 33, 129]
Output = 199

Input:
Index = 2
Array = [4,-2,1,-3,5]
Output = 4 OR 5

Input:
Index = 0
Array = [2124, -173, -155, 146, 193, -30, 2, 186, 102, 4545]
Output = 4545

Input:
Index = 0
Array = [1,0,2,3]
Output = 2

Input:
Index = 2
Array = [3,-1,-3,-2,5]
Output = -1 OR -2
\$\endgroup\$
  • \$\begingroup\$ Could you add a test case where it looks for a result to the left instead of to the right? i.e. 1; [7,1,-4,2] \$\endgroup\$ – Kevin Cruijssen May 4 '17 at 7:43
  • \$\begingroup\$ I think 2; [3,-1,-3,-2,5] is a nice test case. There are positive numbers, but the result is negative. \$\endgroup\$ – Stewie Griffin May 4 '17 at 9:15
  • \$\begingroup\$ Can I use 2-indexed? \$\endgroup\$ – Titus May 4 '17 at 13:29
  • \$\begingroup\$ @Titus I mean if you really want to \$\endgroup\$ – Graviton May 4 '17 at 20:49

21 Answers 21

7
\$\begingroup\$

MATL, 10 bytes

yt&y)>fYk)

This uses 1-based indexing. Try it online!

Explanation

Consider inputs [4,-2,1,-3,5], 3 as an example.

y     % Take two inputs implicitly. Duplicate 2nd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5]
t     % Duplicate top of the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5]
&y    % Duplicate 3rd-top element in the stack
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], [4,-2,1,-3,5], 3
)     % Index: select elements from first input as indicated by second input
      % STACK: [4,-2,1,-3,5], 3, [4,-2,1,-3,5], 1
>     % Greater than, element-wise
      % STACK: [4,-2,1,-3,5], 3, [1,0,0,0,1]
f     % Find: gives indices of non-zero entries
      % STACK: [4,-2,1,-3,5], 3, [1,5]
Yk    % Closest element: gives closest element of each entry in second input
      % ([1,5]) to each entry in the first input (3). In case of a tie it 
      % gives the left-most one
      % STACK: [4,-2,1,-3,5], 1
)     % Index: select elements from first input as indicated by second input
      % STACK: 4
      % Implicitly display
\$\endgroup\$
  • 2
    \$\begingroup\$ Do you have an explanation? \$\endgroup\$ – Nick Clifford May 4 '17 at 0:27
  • \$\begingroup\$ @NickClifford Sure! I was waiting for OP clarification. Explanation added \$\endgroup\$ – Luis Mendo May 4 '17 at 8:42
6
\$\begingroup\$

Jelly, 10 bytes

ị<ṛTạ⁸$ÞḢị

Try it online!

\$\endgroup\$
  • \$\begingroup\$ I was fiddling for ages trying to get sorting to work with the absolute value :( \$\endgroup\$ – Jonathan Allan May 4 '17 at 5:26
5
\$\begingroup\$

Jelly, 11 12 bytes

+1 byte - No wrapping allowed.

Jạż⁸ṢZṪ»\Q2ị

1-indexed.

Try it online!


Previous 11 byter (wrapping indexing), 0-indexed:

ṙżU$Fµ>ḢTḢị
\$\endgroup\$
  • \$\begingroup\$ This fails on e.g. 0 [1,0,2,3]. \$\endgroup\$ – Ørjan Johansen May 4 '17 at 0:18
  • \$\begingroup\$ @ØrjanJohansen Ah - it returns 3, which is 1 away so, um, yeah "nearest" is not defined... \$\endgroup\$ – Jonathan Allan May 4 '17 at 0:21
  • 1
    \$\begingroup\$ I asked OP to add that test case. \$\endgroup\$ – Ørjan Johansen May 4 '17 at 0:27
4
\$\begingroup\$

JavaScript (ES6), 57 55 bytes

Takes the array a and the index i in currying syntax (a)(i).

a=>g=(i,p)=>(x=a[i-p])>a[i]||(x=a[i+p])>a[i]?x:g(i,-~p)

Test cases

let f =

a=>g=(i,p)=>(x=a[i-p])>a[i]||(x=a[i+p])>a[i]?x:g(i,-~p)

console.log(f([-1, 476, 578, 27, 0, 1, -1, 1, 2])(5))

console.log(f([69, 43, 89, 93, 62, 25, 4, 11, 115, 87, 174, 60, 84, 58, 28, 67, 71, 157, 47, 8, 33, 192, 187, 87, 175, 32, 135, 25, 137, 92, 183, 151, 147, 7, 133, 7, 41, 12, 96, 147, 9, 134, 197, 3, 107, 164, 90, 199, 21, 71, 77, 62, 190, 122, 33, 127, 185, 58, 92, 106, 26, 24, 56, 79, 71, 24, 24, 114, 17, 84, 121, 188, 6, 177, 114, 159, 159, 102, 50, 136, 47, 32, 1, 199, 74, 141, 125, 23, 118, 9, 12, 100, 94, 166, 12, 9, 179, 147, 149, 178, 90, 71, 141, 49, 74, 100, 199, 160, 120, 14, 195, 112, 176, 164, 68, 88, 108, 72, 124, 173, 155, 146, 193, 30, 2, 186, 102, 45, 147, 99, 178, 84, 83, 93, 153, 11, 171, 186, 157, 32, 90, 57, 181, 5, 157, 106, 20, 5, 194, 130, 100, 97, 3, 87, 116, 57, 125, 157, 190, 83, 148, 90, 44, 156, 167, 131, 100, 58, 139, 183, 53, 91, 151, 65, 121, 61, 40, 80, 40, 68, 73, 20, 135, 197, 124, 190, 108, 66, 21, 27, 147, 118, 192, 29, 193, 27, 155, 93, 33, 129])(45))

console.log(f([4, -2, 1, -3, 5])(2))

console.log(f([2124, -173, -155, 146, 193, -30, 2, 186, 102, 4545])(0))

\$\endgroup\$
  • \$\begingroup\$ Can you not use | instead of ||? \$\endgroup\$ – Neil May 3 '17 at 23:59
  • \$\begingroup\$ @Neil No, we don't want x to be overwritten when the first condition is fulfilled. \$\endgroup\$ – Arnauld May 4 '17 at 0:13
3
\$\begingroup\$

PHP, 106 Bytes

<?for($y=($a=$_GET[0])[$x=$_GET[1]];$y>=$a[$x-++$i]&&$y>=$a[$x+$i];);echo$y<$a[$x+$i]?$a[$x+$i]:$a[$x-$i];

Online Version

\$\endgroup\$
  • \$\begingroup\$ Looks like these don't work for the first test case. \$\endgroup\$ – Nick Clifford May 3 '17 at 23:14
  • \$\begingroup\$ @NickClifford Now it should work. I have take a wrong approach \$\endgroup\$ – Jörg Hülsermann May 4 '17 at 0:20
3
\$\begingroup\$

Haskell, 48 bytes

i%l=minimum[[j*j,x]|(j,x)<-zip[-i..]l,x>l!!i]!!1

Try it online! Test framework from Ørjan Johansen.

\$\endgroup\$
  • \$\begingroup\$ You can save a byte by using a list and !!1 instead (just change Integer to Int in the header). \$\endgroup\$ – Ørjan Johansen May 4 '17 at 1:51
  • \$\begingroup\$ @ØrjanJohansen Thanks, I had tried that and was unsure why it complained about types. \$\endgroup\$ – xnor May 4 '17 at 1:52
2
\$\begingroup\$

x86-64 Assembly, 40 bytes

Inspired by analyzing Johan du Toit and 2501's C solutions, the following is a function that can be assembled with MASM for x86-64 platforms.

It follows the Microsoft x64 calling convention for passing parameters, so the total length of the array is passed in ECX, the position of interest is passed in EDX, and the pointer to the integer array is passed in R8 (it's a 64-bit platform, so it's a 64-bit pointer).

It returns the result (the "nearest greater number") in EAX.

             FindNearestGreater PROC      
8B F2       \    mov     esi, edx     ; move pos parameter to preferred register
8B D9       |    mov     ebx, ecx     ; make copy of count (ecx == i; ebx == count)
            | MainLoop:
8B C6       |    mov     eax, esi     ; temp  = pos
2B C1       |    sub     eax, ecx     ; temp -= i
99          |    cdq
33 C2       |    xor     eax, edx
2B C2       |    sub     eax, edx     ; temp = AbsValue(temp)
            | 
41 8B 14 B0 |    mov     edx, DWORD PTR [r8+rsi*4]
41 39 14 88 |    cmp     DWORD PTR [r8+rcx*4], edx
7E 04       |    jle     KeepGoing    ; jump if (pValues[i] <= pValues[pos])
3B D8       |    cmp     ebx, eax
77 02       |    ja      Next         ; jump if (count > temp)
            | KeepGoing:
8B C3       |     mov     eax, ebx    ; temp = count
            | Next:
8B D8       |     mov     ebx, eax    ; count = temp
E2 E3       |     loop    MainLoop    ; equivalent to dec ecx + jnz, but smaller (and slower)
            | 
            |     ; Return pValues[temp + pos]
03 C6       |     add     eax, esi
41 8B 04 80 |     mov     eax, DWORD PTR [r8+rax*4]
C3          /     ret
             FindNearestGreater ENDP

If you wanted to call it from C code, the prototype would be:

extern int FindNearestGreater(unsigned int count,
                              unsigned int pos,
                              const    int *pValues);
\$\endgroup\$
1
\$\begingroup\$

Ruby, 64 bytes

->a,i{a[(0...a.size).select{|j|a[j]>a[i]}.min_by{|j|(i-j).abs}]}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Ohm, 20 bytes

Basically a translation of this Ruby answer.

Dl#)░┼_ª┼┘ª>;╥┘_-A;ª

Try it online!

Explanation will come later when I'm not doing homework.

\$\endgroup\$
1
\$\begingroup\$

Haskell, 53 bytes

(#) takes an Int and a list of Ints or Integers (actually any Ord type), and returns an element of the list.

n#l=[x|i<-[1..],x:_<-(`drop`l)<$>[n-i,n+i],x>l!!n]!!0

How it works

  • n is the given index and l is the given list/"array".
  • i, taking on values from 1 upwards, is the distance from n currently being tested.
  • For each i, we check indices n-i and n+i.
  • x is the element of l being tested. If it passes the tests it will be an element of the resulting list comprehension.
    • Indexing arbitrary indices with !! could give an out of bounds error, while drop instead returns either the whole list or an empty list in that case. The pattern match with x:_ checks that the result is not empty.
    • x>l!!n tests that our element is greater than the element at index n (which is guaranteed to exist).
    • !!0 at the end returns the first match/element of the list comprehension.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python, 62 bytes

lambda a,i:min((v<=a[i],abs(j-i),v)for j,v in enumerate(a))[2]

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Brachylog, 17 bytes

hH&∋₎<.&t:I≜+:H∋₍

Try it online!

Explanation

hH                      Call the list H
  &∋₎<.                 Output is greater than the number at the specified index
       &t:I≜            Label I (0, then 1, then -1, then 2, then -2, …)
            +           Sum I with the input Index
             :H∋₍       Output is the element of H at index <the sum>
\$\endgroup\$
1
\$\begingroup\$

Java (OpenJDK 8), 98 bytes

int f(int n,int[]a){for(int s=1,i=1,x=a[n];;n+=i++*s,s=-s)if(0<=n&n<a.length&&a[n]>x)return a[n];}

Try it online!

Checks the indices in the order specified by the partial sums of the following sum:

initial value + 1 - 2 + 3 - 4 + 5 - 6 + ...
\$\endgroup\$
  • \$\begingroup\$ I was just reading the question and wanted to start writing an answer.. Btw, why the s=1, and ,s=-s, it has no use in your answer.. Did you forgot to remove it from an old approach? \$\endgroup\$ – Kevin Cruijssen May 4 '17 at 7:35
  • 1
    \$\begingroup\$ @KevinCruijssen it is a mistake and I'm fixing it now. It passed the testcases because in all those testcases, the nearest greater number is to the right. \$\endgroup\$ – Leaky Nun May 4 '17 at 7:36
1
\$\begingroup\$

C, 69 bytes

t;b;f(*d,c,p){for(b=c;c--;)d[c]>d[p]&(t=abs(p-c))<b?b=t:0;*d=d[p+b];}

First argument is an in/out argument. Output is stored in its first element.

See it work online.

\$\endgroup\$
1
\$\begingroup\$

R, 59 bytes

function(l,i)l[j<-l>l[i]][which.min(abs(1:length(l)-i)[j])]

returns an anonymous function. In the event that there are two elements greater at equal distances, will return the first (lesser index).

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Pyth - 28 bytes

JEehf>@T1@JQo@NZm(adQ@Jd)UlJ

Try it

\$\endgroup\$
1
\$\begingroup\$

PHP, 73 bytes

function($i,$a){for(;$b<=$a[$i];)$b=max($a[++$d+$i],$a[$i-$d]);return$b;}

closure takes 0-based index and array from arguments. Verify all test cases.

\$\endgroup\$
  • \$\begingroup\$ Not the next higher value. You need a value with the lowest distance that is higher \$\endgroup\$ – Jörg Hülsermann May 4 '17 at 22:24
  • \$\begingroup\$ @JörgHülsermann Thanks for pointing out. \$\endgroup\$ – Titus May 5 '17 at 9:23
0
\$\begingroup\$

Pyth, 16 bytes

JEh>#@JQ@LJaDQUJ

Test suite.

\$\endgroup\$
0
\$\begingroup\$

C, 110 bytes

c,o;e(g,l,f)int*g;{for(o=g[l],c=1;c<f;c++)l+c<f&&g[l+c]>o?o=g[l+c],c=f:0,l-c>=0&&g[l-c]>o?o=g[l-c],c=f:0;g=o;}

Try it online

\$\endgroup\$
0
\$\begingroup\$

Java, 96 Bytes

int f(int n,int[]a){for(int s=1,i=1,x=a[n];0>(n+=i++*s)|n>=a.length||a[n]<=x;s=-s);return a[n];}

Identifiers are named like @Leaky Nun's answer. Furthermore, most parts have been aligned to be basically the same: In comparison, the if has been replaced by the for-condition (sacrificing the additional semicolon). A colon has been removed by moving increment-part into condition (so the parentheses of the previous if-statement practically "moved") - changing & to | did not have impact on character count.

\$\endgroup\$
0
\$\begingroup\$

Clojure, 95 bytes

#(%(nth(nth(sort-by first(for[i(range(count %)):when(>(% i)(% %2))][(Math/abs(- i %2))i]))0)1))

This is the shortest I could come up with :( I also tried playing around with this but couldn't bring it to the finish line:

#(map(fn[f c](f c))[reverse rest](split-at %2 %))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.