Author |
Topic: Find a sequence from an array (Read 3917 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
Addicted!!!
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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print