Find the nearest greater number

Question

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.

This is code-golf so the shortest code in bytes wins

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

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] — Kevin Cruijssen, May 4, 2017 at 7:43
I think 2; [3,-1,-3,-2,5] is a nice test case. There are positive numbers, but the result is negative. — Stewie Griffin, May 4, 2017 at 9:15

Community · Accepted Answer · 2020-06-17 09:04:33Z

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

@NickClifford Sure! I was waiting for OP clarification. Explanation added — Luis Mendo, May 4, 2017 at 8:42

Dennis · Accepted Answer · 2017-05-04 03:24:51Z

6

Jelly, 10 bytes

ị<ṛTạ⁸$ÞḢị

Try it online!

answered May 4, 2017 at 3:24

Dennis

210k41 gold badges368 silver badges819 bronze badges

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

Add a comment |

Jonathan Allan · Accepted Answer · 2017-05-04 02:30:14Z

5

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Ḣị

edited May 4, 2017 at 2:30

answered May 3, 2017 at 23:27

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

\$\begingroup\$ This fails on e.g. 0 [1,0,2,3]. \$\endgroup\$
– Ørjan Johansen
May 4, 2017 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, 2017 at 0:21
1

\$\begingroup\$ I asked OP to add that test case. \$\endgroup\$
– Ørjan Johansen
May 4, 2017 at 0:27

Add a comment |

Arnauld · Accepted Answer · 2017-05-03 23:49:22Z

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))

@Neil No, we don't want x to be overwritten when the first condition is fulfilled. — Arnauld, May 4, 2017 at 0:13

Jörg Hülsermann · Accepted Answer · 2017-05-04 00:18:23Z

3

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

edited May 4, 2017 at 0:18

answered May 3, 2017 at 22:34

Jörg Hülsermann

13.3k3 gold badges14 silver badges36 bronze badges

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

Add a comment |

xnor · Accepted Answer · 2017-05-04 01:54:26Z

3

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.

edited May 4, 2017 at 1:54

answered May 4, 2017 at 1:36

xnor

144k26 gold badges273 silver badges637 bronze badges

\$\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, 2017 at 1:51
\$\begingroup\$ @ØrjanJohansen Thanks, I had tried that and was unsure why it complained about types. \$\endgroup\$
– xnor
May 4, 2017 at 1:52

Add a comment |

Jonathan Allan · Accepted Answer · 2017-05-04 06:03:53Z

2

Python, 62 bytes

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

Try it online!

edited May 4, 2017 at 6:03

answered May 4, 2017 at 5:49

Jonathan Allan

104k7 gold badges62 silver badges270 bronze badges

Add a comment |

Cody Gray - on strike · Accepted Answer · 2017-05-04 14:39:00Z

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);

Value Ink · Accepted Answer · 2017-05-03 23:04:44Z

1

Ruby, 64 bytes

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

Try it online!

answered May 3, 2017 at 23:04

Value Ink

12.5k1 gold badge16 silver badges42 bronze badges

Add a comment |

Nick Clifford · Accepted Answer · 2017-05-03 23:22:44Z

1

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.

answered May 3, 2017 at 23:22

Nick Clifford

1,2321 gold badge9 silver badges14 bronze badges

Add a comment |

Ørjan Johansen · Accepted Answer · 2017-05-04 00:13:13Z

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!

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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>

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 4, 2017 at 7:13

Fatalize

38.4k5 gold badges67 silver badges160 bronze badges

Add a comment |

Leaky Nun · Accepted Answer · 2017-05-04 07:38:30Z

1

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 + ...

edited May 4, 2017 at 7:38

answered May 4, 2017 at 7:31

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

\$\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, 2017 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, 2017 at 7:36

Add a comment |

5 revs · Accepted Answer · 2017-05-04 16:35:39Z

1

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.

edited May 4, 2017 at 16:35

community wiki

5 revs
2501

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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!

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 4, 2017 at 17:03

Giuseppe

28.1k3 gold badges30 silver badges101 bronze badges

Add a comment |

Maria · Accepted Answer · 2017-05-04 22:12:53Z

1

Pyth - 28 bytes

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

Try it

edited May 4, 2017 at 22:12

answered May 3, 2017 at 23:36

Maria

6423 silver badges6 bronze badges

Add a comment |

Johannes · Accepted Answer · 2017-05-05 08:30:44Z

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.

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered May 4, 2017 at 13:37

Titus

14.6k1 gold badge23 silver badges41 bronze badges

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

Add a comment |

caird coinheringaahin g · Accepted Answer · 2021-02-14 16:10:53Z

1

Jelly, 9 bytes

>ị@TạÞị⁸Ḣ

Try it online!

How it works

>ị@TạÞị⁸Ḣ - Main link. Takes the array A on the left and the index i on the right
 ị@       - Get the i'th element of A, k
>         - Is k greater than each element of A?
   T      - Get the indices of the 1s
     Þ    - Sort these indices by:
    ạ     -   Absolute difference with i
      ị⁸  - Index back into A
        Ḣ - Take the first element

answered Feb 14, 2021 at 16:10

caird coinheringaahin g♦

49.4k11 gold badges121 silver badges348 bronze badges

Add a comment |

Leaky Nun · Accepted Answer · 2017-05-04 03:07:18Z

0

Pyth, 16 bytes

JEh>#@JQ@LJaDQUJ

Test suite.

edited May 4, 2017 at 3:07

answered May 4, 2017 at 2:56

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

Add a comment |

NikoNyrh · Accepted Answer · 2017-05-05 08:55:20Z

0

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 %))

answered May 5, 2017 at 8:55

NikoNyrh

2,6319 silver badges8 bronze badges

Add a comment |

l4m2 · Accepted Answer · 2021-02-16 13:17:38Z

0

JavaScript, 44 bytes

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

Try it online!

from https://codegolf.stackexchange.com/a/118765/

answered Feb 16, 2021 at 13:17

l4m2

20.5k2 gold badges19 silver badges85 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2021-02-16 13:45:58Z

05AB1E, 10 bytes

è›ƶ0K<¹.xè

0-based indexing.

Try it online or verify all test cases.

Explanation:

è           # Get the item in the second (implicit) input-list at the first (implicit)
            # input-index
 ›          # Check for each value in the second (implicit) input-list if it's larger
            # than this value (1 if truthy; 0 if falsey)
  ƶ         # Multiply each by its 1-based index
   0K       # Remove all 0s from this list
     <      # Decrease each value by 1 to make it a 0-based index
      ¹.x   # Pop the list and get the item closest to the first input-index
         è  # Use that to index into the second (implicit) input-list
            # (after which the result is output implicitly)

jdt · Accepted Answer · 2021-09-21 15:44:46Z

0

C (gcc), 110 108 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&&g[l-c]>o?o=g[l-c],c=f:0;g=o;}

-2 bytes thanks to ceilingcat!!

Try it online!

edited Sep 21, 2021 at 15:44

answered May 4, 2017 at 6:45

jdt

3,4321 gold badge11 silver badges17 bronze badges

\$\begingroup\$ Suggest l/c instead of l>=c \$\endgroup\$
– ceilingcat
Sep 27, 2021 at 20:20

Add a comment |

Shaggy · Accepted Answer · 2021-09-21 16:56:36Z

0

Japt `-g`, 11 bytes

gUð>UgV)ñaV

Try it

answered Sep 21, 2021 at 16:56

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Nicholas Charles · Accepted Answer · 2021-09-22 14:15:04Z

0

APL(Dyadic Classic), 21 bytes

A[1↑{⍵[⍋|I-⍵]}⍸A>I⌷A]

Try it online!

edited Sep 22, 2021 at 14:15

answered Sep 22, 2021 at 13:44

Nicholas Charles

12 bronze badges

\$\begingroup\$ Welcome to code golf, and nice first answer! Make sure to check out our tips for golfing in APL to see if there's any way to golf your code. \$\endgroup\$
– Aaroneous Miller
Sep 22, 2021 at 14:18

Add a comment |

Yousername · Accepted Answer · 2021-09-24 20:52:06Z

0

TI-Basic, 46 bytes

Prompt A
Prompt I
seq(abs(J-I),J,1,dim(ʟA→B
SortA(ʟB,ʟA
ʟA(1+sum(not(cumSum(ʟA>ʟA(1

Index is 1-based. Output is stored in Ans and is displayed at the end.

answered Sep 24, 2021 at 20:52

Yousername

3,6509 silver badges24 bronze badges

Add a comment |

Find the nearest greater number

The task

Assumptions

I/O pairs

27 Answers 27

MATL, 10 bytes

Explanation

Jelly, 10 bytes

Jelly, 11 12 bytes

JavaScript (ES6), 57 55 bytes

Test cases

PHP, 106 Bytes

Haskell, 48 bytes

Python, 62 bytes

x86-64 Assembly, 40 bytes

Ruby, 64 bytes

Ohm, 20 bytes

Haskell, 53 bytes

How it works

Brachylog, 17 bytes

Explanation

Java (OpenJDK 8), 98 bytes

C, 69 bytes

R, 59 bytes

Pyth - 28 bytes

PHP, 73 bytes

Jelly, 9 bytes

How it works

Pyth, 16 bytes

Clojure, 95 bytes

JavaScript, 44 bytes

05AB1E, 10 bytes

C (gcc), 110 108 bytes

Japt -g, 11 bytes

APL(Dyadic Classic), 21 bytes

TI-Basic, 46 bytes

Your Answer

Sign up or log in

Post as a guest

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

Linked

Related

Hot Network Questions

Japt `-g`, 11 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
array
integer
or ask your own question.