wu :: forums « wu :: forums - Find a sequence from an array » Welcome, Guest. Please Login or Register. Sep 7th, 2024, 9:46am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    cs (Moderators: towr, william wu, Grimbal, SMQ, Icarus, ThudnBlunder, Eigenray)    Find a sequence from an array « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Find a sequence from an array  (Read 3926 times)
Ved
Junior Member

Gender:
Posts: 53
 Find a sequence from an array   « on: Feb 15th, 2012, 3:26am » Quote Modify

Given an int array which might contain duplicates, find if it is a sequence.
Eg. {45,50,47,46,49,48}
is a sequence 45, 46,47,48,49,50

Sorting is an obvious solution. Can this be done in O(n) time and O(1) space
 IP Logged
A
Full Member

Perder todas as esperanças é liberdade!

Gender:
Posts: 236
 Re: Find a sequence from an array   « Reply #1 on: Feb 15th, 2012, 8:27am » Quote Modify

Using MIN and MAX of the array, we need to check if elements from 1 to N are present.
Assuming array is writable,

if MAX - MIN + 1 NOT EQUAL to size of array => duplicates

A[i] = A[i]-MIN+1 for all i = 1 to n

 IP Logged

What Doesn't Kill Me Will Only Make Me Stronger
Ved
Junior Member

Gender:
Posts: 53
 Re: Find a sequence from an array   « Reply #2 on: Feb 15th, 2012, 9:43pm » Quote Modify

I dont get part- A[i] = A[i]-MIN+1 for all i = 1 to n
What that gives is :
1,6,3,2,5,4 - so how do I find the sequence. sorry but I am missing the point here.
 IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Find a sequence from an array   « Reply #3 on: Feb 15th, 2012, 10:08pm » Quote Modify

Once you know the minimum, you can sort the array in O(n) time if the array forms a sequence. Because you can calculate based on the value were each element should go.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
R
Senior Riddler

Gender:
Posts: 502
 Re: Find a sequence from an array   « Reply #4 on: Sep 14th, 2012, 9:22pm » Quote Modify

[5, 3, 1, 6, 1, 2, 4, 3]

What is the expected answer for the above array? Does it have a sequence? i.e. while looking for a sequence, can I ignore duplicates?
 IP Logged

The first experience seems like Magic, but the second tells you the Trick behind it.
akasina9
Newbie

x = 0x2B | ~ 0x2B. x is the question

Gender:
Posts: 9
 Re: Find a sequence from an array   « Reply #5 on: Nov 15th, 2012, 9:43am » Quote Modify

on Feb 15th, 2012, 8:27am, R0B1N wrote:
 Using MIN and MAX of the array, we need to check if elements from 1 to N are present. Assuming array is writable,     if MAX - MIN + 1 NOT EQUAL to size of array => duplicates     A[i] = A[i]-MIN+1 for all i = 1 to n

Don't you mean:
new_index = A[i] - MIN + 1
in the sorted array?
 IP Logged
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft => cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »