Member Avatar for evilsithgirl

i'm trying to write an algorithm for this problem

given n<2m numbers of m bits each design an O(n) time algorithm that finds an m-bit number that is different from all of the n given numbers. comparison is done in O(1) time.

my question is this. if i use a sort algorithm (say merge sort) which is O(nlogn) and then a for loop to check all the numbers against a number i've made (which would be O(n)), does this make the algorithm run time O(n)? or O(n+nlogn)?

any help would be greatly appreciated including tips on the algorithm design. I am quite stumpted on how to design this. I know that a for loop can do comparisons in O(n) with an if statement, but unless the array of numbers is pre-sorted, it won't work

  • 3 Contributors
  • 6 Replies
  • 133 Views
  • 3 Days Discussion Span
  • Latest Post Latest Post by abhimanipal
Member Avatar for BestJewSinceJC

If you use merge sort to sort anything at all, your algorithm will be at least O(nlgn), so your algorithm will not meet the qualifications. In fact, you cannot use any comparison sorting algorithm, (merge sort being an example of one) because any comparison sort is at least O(nlgn).

Look into bucket sort, radix sort, etc. I don't know which one will work for your problem. Someone else here probably does so you may want to wait for their input.
http://en.wikipedia.org/wiki/Bucket_sort

Edited by BestJewSinceJC because: n/a
Member Avatar for abhimanipal

What exactly do you mean by different from all numbers ??? Does it mean that the array has contains many elements with many duplicates, but one element has only 1 copy ?

Make a 2-D array temp of size n. This array will store the element and the number of times this element has occurred
Initialize the temp array to 0

Scan through the input array. If you get an element say 10,
temp.element=10
temp.count++;
i++

Scan the temp array.
If temp.count is 0, then the element i occurs just once in the input array
else the element i occurs more than once

Run time of this algo is O(n). Space complexity is O(2n)

Edited by abhimanipal because: n/a
Member Avatar for BestJewSinceJC

What exactly do you mean by different from all numbers ??? Does it mean that the array has contains many elements with many duplicates, but one element has only 1 copy ?

She means come up with an m-bit number that is different than every number in the array. She wants an algorithm that will do this in O(n) time. And the fact that there are m bits but < 2m total numbers means that it is guaranteed to be possible to do this task. Your algorithm doesn't work for this problem. I'm hoping someone can point her in the right direction because I'm also interested in seeing where this one goes.

Edited by BestJewSinceJC because: n/a
Member Avatar for abhimanipal

I think my algorithm has complexity of O(n).

The size of the temp buffer is n . It takes time O(n) to build this temp buffer and time O(n) to scan across this buffer.
O(n) + O(n) = O(n)

unless I am missing some thing

Member Avatar for BestJewSinceJC

I'm not arguing with that. Your algorithm just doesn't solve the specified problem, regardless of time complexity.

Member Avatar for abhimanipal

I am sorry but I do not understand why does this algorithm not solve the problem....
Can you give some sample input where the algorithm will fail ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.