wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Find a sequence from an array
        
(Message started by: Ved on Feb 15^th, 2012, 3:26am)

Title: Find a sequence from an array
Post by Ved on Feb 15^th, 2012, 3:26am

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

Title: Re: Find a sequence from an array
Post by R0B1N on Feb 15^th, 2012, 8:27am

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

Title: Re: Find a sequence from an array
Post by Ved on Feb 15^th, 2012, 9:43pm

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.

Title: Re: Find a sequence from an array
Post by towr on Feb 15^th, 2012, 10:08pm

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.

Title: Re: Find a sequence from an array
Post by R on Sep 14^th, 2012, 9:22pm

[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?

Title: Re: Find a sequence from an array
Post by akasina9 on Nov 15^th, 2012, 9:43am

on 02/15/12 at 08:27:35, R0B1N wrote:

Don't you mean:
new_index = A[i] - MIN + 1
in the sorted array?