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.

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

I'd like to suggest a 0 [1,0,2,3] test case, as some of our implementations disagree on whether it should be 2 or 3. — Ørjan Johansen, 9 hours ago
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, 2 hours ago

Luis Mendo · Answer 1 · 2017-05-04 08:42:02Z

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, 1 hour ago

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

up vote 4 down vote

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 7 hours ago

answered 10 hours ago

Jonathan Allan

21.9k31284

This fails on e.g. 0 [1,0,2,3]. – Ørjan Johansen 9 hours ago

@ØrjanJohansen Ah - it returns 3, which is 1 away so, um, yeah "nearest" is not defined... – Jonathan Allan 9 hours ago

1

I asked OP to add that test case. – Ørjan Johansen 9 hours ago

add a comment |

Arnauld · Answer 3 · 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, 10 hours ago

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

up vote 2 down vote

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 10 hours ago

answered 11 hours ago

Jörg Hülsermann

5,7642526

Looks like these don't work for the first test case. – Nick Clifford 11 hours ago

@NickClifford Now it should work. I have take a wrong approach – Jörg Hülsermann 9 hours ago

add a comment |

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

up vote 2 down vote

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 8 hours ago

answered 8 hours ago

xnor

62k11127317

You can save a byte by using a list and !!1 instead (just change Integer to Int in the header). – Ørjan Johansen 8 hours ago

@ØrjanJohansen Thanks, I had tried that and was unsure why it complained about types. – xnor 8 hours ago

add a comment |

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

up vote 2 down vote

Jelly, 10 bytes

ị<ṛTạ⁸$ÞḢị

Try it online!

answered 6 hours ago

Dennis♦

139k25243583

I was fiddling for ages trying to get sorting to work with the absolute value :( – Jonathan Allan 4 hours ago

add a comment |

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

up vote 1 down vote

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 11 hours ago

Value Ink

5,850524

add a comment |

Uriel · Answer 8 · 2017-05-03 23:38:24Z

up vote 1 down vote

Python, 79 bytes

lambda a,i:a[min([j for j in range(len(a))if a[j]>a[i]],key=lambda j:abs(j-i))]

edited 10 hours ago

answered 10 hours ago

Uriel

1,289210

add a comment |

Ørjan Johansen · Answer 9 · 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!

Fatalize · Answer 10 · 2017-05-04 07:13:11Z

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>

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

up vote 1 down vote

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 2 hours ago

answered 2 hours ago

Leaky Nun

20.3k252149

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? – Kevin Cruijssen 2 hours ago

1

@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. – Leaky Nun 2 hours ago

add a comment |

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

up vote 0 down vote

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 10 hours ago

Nick Clifford

814211

add a comment |

Svetlana · Answer 13 · 2017-05-03 23:36:44Z

up vote 0 down vote

Pyth - 28 bytes

JEhf>T@JQm@J+Q?%d2/d2_/d2SlJ

Try it

answered 10 hours ago

Svetlana

2394

?%d2/d2_/d2 can be replaced with @_B/d2%d2 – Leaky Nun 7 hours ago

f>T@JQ can be replaced with >#@JQ – Leaky Nun 7 hours ago

However, your code fails on this input. – Leaky Nun 7 hours ago

add a comment |

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

up vote 0 down vote

Pyth, 16 bytes

JEh>#@JQ@LJaDQUJ

Test suite.

edited 7 hours ago

answered 7 hours ago

Leaky Nun

20.3k252149

add a comment |

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

up vote 0 down vote

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 4 hours ago

answered 4 hours ago

Jonathan Allan

21.9k31284

add a comment |

Johan du Toit · Answer 16 · 2017-05-04 06:45:43Z

up vote 0 down vote

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

answered 3 hours ago

Johan du Toit

74716

add a comment |

asked	today
viewed	516 times
active	today

current community

your communities

more stack exchange communities

Find the nearest greater number

The task

Assumptions

I/O pairs

16 Answers 16

MATL, 10 bytes

Explanation

Jelly, 11 12 bytes

JavaScript (ES6), 57 55 bytes

Test cases

PHP, 106 Bytes

Haskell, 48 bytes

Jelly, 10 bytes

Ruby, 64 bytes

Python, 79 bytes

Haskell, 53 bytes

How it works

Brachylog, 17 bytes

Explanation

Java (OpenJDK 8), 98 bytes

Ohm, 20 bytes

Pyth - 28 bytes

Pyth, 16 bytes

Python, 62 bytes

C, 110 bytes

Your Answer

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

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Find the nearest greater number

The task

Assumptions

I/O pairs

16 Answers 16

MATL, 10 bytes

Explanation

Jelly, 11 12 bytes

JavaScript (ES6), 57 55 bytes

Test cases

PHP, 106 Bytes

Haskell, 48 bytes

Jelly, 10 bytes

Ruby, 64 bytes

Python, 79 bytes

Haskell, 53 bytes

How it works

Brachylog, 17 bytes

Explanation

Java (OpenJDK 8), 98 bytes

Ohm, 20 bytes

Pyth - 28 bytes

Pyth, 16 bytes

Python, 62 bytes

C, 110 bytes

Your Answer

Sign up or log in

Post as a guest

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

Visit Chat

Related

Hot Network Questions