Author |
Topic: two questions (Read 1547 times) |
|
oriole
Newbie
Posts: 32
|
 |
two questions
« on: Jun 30th, 2008, 7:42am » |
 Quote  Modify
|
1. An array 1..n is given with duplicates in random positions. We have to print them in right order.
e.g. Input
5,12,6,8,6,12,5,2
Output
5,5,12,12,6,6,8,2
IMO we can use hash table for keeping a count of the entries.
Is there a better way?
2. Given a array 1...n with distinct elements 1..(n+1).
Find the missing element.
What if k elements are missing?
IMO.. its easy to find single missing element
((sum of all elements) - (n(n+1))/2) + 1
In case of k elements we can sort in O(n log n) time and traverse the list printing the elements simultaneously..
Any better algorithm..
|
| « Last Edit: Jun 30th, 2008, 7:43am by oriole » |
 IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender: 
Posts: 1001
|
|
Re: two questions
« Reply #1 on: Jun 30th, 2008, 12:31pm » |
Quote Modify
|
on Jun 30th, 2008, 7:42am, oriole wrote:IMO.. its easy to find single missing element
((sum of all elements) - (n(n+1))/2) + 1 |
|
Did you mean,
((n+1)(n+2)/2 - sum_of_all_elements)
??
Quote:| In case of k elements we can sort in O(n log n) time and traverse the list printing the elements simultaneously.. Any better algorithm.. |
|
Since it is between 1..n+1, you can possibly sort it a bit more efficiently using k extra variable.
Code:public class MissingElements {
...public static void main(String[] args) {
......int k = 5;
......int n = 5;
......// size of A is n+k
......int[] A = {9, 3, 2, 7, 5, -1, -1, -1, -1, -1};
......int i = 0;
......int count = 0;
......while (i < A.length) {
.........if (A[i] == -1) {
............i++;
............continue;
.........}
.........if (A[i] != i+1) {
............int temp = A[i];
............A[i] = A[A[i] - 1];
............A[temp - 1] = temp;
............count++;
............if (count > n - 1) {
...............count = 0;
...............i++;
............}
.........} else {
............count = 0;
............i++;
.........}
......}
......for (int j = 0; j < A.length; j++) {
.........if (A[j] == -1)
............System.out.println(j+1);
.........}
...}
} |
|
[edit]Ofcourse, there is an easy way. Just initialize a new array B of size n+1 and assign
B[A[i]] = A[i]. Go through B and find all the missing elements.[/edit]
-- AI
|
| « Last Edit: Jun 30th, 2008, 12:49pm by TenaliRaman » |
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: two questions
« Reply #2 on: Jun 30th, 2008, 12:49pm » |
Quote Modify
|
on Jun 30th, 2008, 12:31pm, TenaliRaman wrote:| Since it is between 1..n+1, you can possibly sort it a bit more efficiently using k extra variable. |
|
I don't see a constant space requirement. So you could just declare a n+k length bit-array set to 0, and flip the bit for each element in the input, then return the numbers corresponding to the positions left with 0.
It a bit more wasteful then your algorithm, and the idea behind it is equivalent. But it's simpler to write (and read, once written).
|
| « Last Edit: Jun 30th, 2008, 12:50pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: two questions
« Reply #3 on: Jun 30th, 2008, 12:51pm » |
Quote Modify
|
on Jun 30th, 2008, 12:49pm, towr wrote:| I don't see a constant space requirement. So you could just declare a n+k length bit-array set to 0, and flip the bit for each element in the input, then return the numbers corresponding to the positions left with 0. |
|
Just did an edit [ ].
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: two questions
« Reply #4 on: Jun 30th, 2008, 12:53pm » |
Quote Modify
|
on Jun 30th, 2008, 12:51pm, TenaliRaman wrote:| Just did an edit []. |
|
Yeah, at almost the exact time I posted. I'm not even sure if it was slightly before or slightly after. But independently, at least.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
oriole
Newbie
Posts: 32
|
|
Re: two questions
« Reply #5 on: Jun 30th, 2008, 6:25pm » |
Quote Modify
|
but if do have a space constraint then 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: two questions
« Reply #6 on: Jul 1st, 2008, 12:57am » |
Quote Modify
|
on Jun 30th, 2008, 6:25pm, oriole wrote:| but if do have a space constraint then |
|
Then as long as it's O(k) space, TenaliRaman's code should work fine. If space is more limited still, you may have to resort to a general sort.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
oriole
Newbie
Posts: 32
|
|
Re: two questions
« Reply #7 on: Jul 1st, 2008, 6:31am » |
Quote Modify
|
Ok.. understood that..
any views on first question ?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: two questions
« Reply #8 on: Jul 1st, 2008, 6:34am » |
Quote Modify
|
on Jul 1st, 2008, 6:31am, oriole wrote:| any views on first question ? |
|
I can't think of anything better than using a hashtable; and that's what you already suggested yourself.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print