array riddle in c

[puzzlecracker]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

 

[xarax]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

Please try to do your own homework. If you need
help, then ask your teacher. Be sure to ask your
teacher what O(n) means, then the answer should
become obvious.

 

[puzzlecracker]

bit vector
No extra space!

 

[Keith Thompson]

No extra space!

If you're going to post these problems, please state all the
requirements in your initial post. It's hardly fair to impose
additional restrictions after someone has posted a valid solution to
the original problem.

 

[Ben Pfaff]

No extra space!

You said you wanted an O(n) algorithm. How do you expect anyone
to solve your "riddle" if you keep adding more stipulations?

 

[puzzlecracker]

Given an array of size n, and its populated with consecutive integers
from 1
to n, i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them WITHOUT using extra space?


I am sorry for the confusion and solution with
bit vector is nonetheless great!

Actually, there are 2 solutions for this problem that I can think of
without using extra storage

 

[Keith Thompson]

Given an array of size n, and its populated with consecutive integers
from 1
to n, i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them WITHOUT using extra space?

Does that mean the solution can't declare variables? Or did you mean
without using more than O(1) extra space?

 

[Ben Pfaff]

Given an array of size n, and its populated with consecutive integers
from 1
to n, i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them WITHOUT using extra space?

I expect that any solution would require at least O(1) extra
space.

 

[puzzlecracker]

latter, sure you can declare variables. Sorry for lack of formality,
next time I'll be more formal in providing the description... good luck!

 

[Keith Thompson]

latter, sure you can declare variables. Sorry for lack of formality,
next time I'll be more formal in providing the description... good luck!

You have again posted a followup with no context.

Usenet is an asynchronous medium. Articles often arrive out of order;
readers can see followup articles before the original article arrives
on the server.

In other words, many of your readers may have no idea what you're
referring to when you write "latter".

Based on context, I'm reasonably sure you were referring to my own
article:

] > Given an array of size n, and its populated with consecutive integers
] > from 1
] > to n, i.e. [1, 2...n-1, n] in random order. Two integers are removed,
] > meaning zero is placed in their places. Give O (n) efficient algorithm
] > to find them WITHOUT using extra space?
]
] Does that mean the solution can't declare variables? Or did you mean
] without using more than O(1) extra space?

but following your article's "References:" header leads only to your
own previous article. You responded to my article by posting a
followup to your own.

I know that groups.google.com has some serious bugs, but the one that
you're running into has an easy workaround.

"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

I've written this several times, and CBFalconer has been using it as
his sig quote. Multiple people have told you about this multiple
times.

If it's worth your time and effort to post, it's worth your time and
effort to do it properly. If you choose not to, it's not worth my
time and effort to track down what you're talking about.

 

[Harshan]

Hello


You know n*(n+1)/2 gives the sum of n consetive numbers .

Subtract the sum from the actual sum of numbers

You will get the sum of two numbers a + b = sum

then proceed with your skills to find the a and b

 

[Allan Bruce]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

erm, isnt this trivial? All you want is to find where they are?

for (loop=0; loop<n; loop++)
if (array[loop] == 0)
printf("0 found at position %d\n", loop);

should do the trick! Or perhaps you should re-write the question ;-)
Allan

 

[pete]

Given an array of size n and populated with
consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order.
Two integers are removed,
meaning zero is placed in their places.
Give O (n) efficient algorithm
to find them?

erm, isnt this trivial? All you want is to find where they are?

for (loop=0; loop<n; loop++)
if (array[loop] == 0)
printf("0 found at position %d\n", loop);

should do the trick! Or perhaps you should re-write the question ;-)
Allan

He said "in random order"

 

[REH]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

erm, isnt this trivial? All you want is to find where they are?

for (loop=0; loop<n; loop++)
if (array[loop] == 0)
printf("0 found at position %d\n", loop);

should do the trick! Or perhaps you should re-write the question ;-)
Allan

I said that numbers areNOT sorted (random order) -- what you wrote is
wrong!
this question was asked by the microsoft folks

How is he wrong? He found all the zeroes in O(n) time, and without
depending on the array being sorted. You emphasized "not" but where did he
depend on the array's order?

 

[Rufus V. Smith]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

erm, isnt this trivial? All you want is to find where they are?

for (loop=0; loop<n; loop++)
if (array[loop] == 0)
printf("0 found at position %d\n", loop);

should do the trick! Or perhaps you should re-write the question ;-)
Allan

I said that numbers areNOT sorted (random order) -- what you wrote is
wrong!
this question was asked by the microsoft folks

It was a poorly stated question.

The solution given does, in fact, find where the zeros are.

It doesn't tell which integers were removed.

Rufus

 

[Default User]

luck!

You have again posted a followup with no context.

Usenet is an asynchronous medium. Articles often arrive out of order;
readers can see followup articles before the original article arrives
on the server.

Why do people keep replying to this idiot (puzzlecracker)? He
constantly posts off-topic threads, most of the rest is this type of
stupid "here figure this out" crap. When he does, he usually refuses to
use proper usenet etiquette and quote messages properly, even though
he's been instructed several times on how to that.
I'm plonking him, I'm just plain old tired of his behavior.



Brian

 

[m]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

it can be solved in 2 loops still being O(n)
first loop goes thru numbers in array and indexes another array with 1
or 0 for found or not found

array a of size n and array b of size n each initialized to 0
go thru a and st b(a(i)) = 1
go thru b and indexes = 0 are the ones not in a.

 

[m]

Given an array of size n and populated with consecutive integers from 1
to n i.e. [1, 2...n-1, n] in random order. Two integers are removed,
meaning zero is placed in their places. Give O (n) efficient algorithm
to find them?

it can be solved in 2 loops still being O(n)
first loop goes thru numbers in array and indexes another array with 1
or 0 for found or not found

array a of size n and array b of size n each initialized to 0
go thru a and st b(a(i)) = 1
go thru b and indexes = 0 are the ones not in a.

*should read b(i) initialized to 0

 

[pete]

Given an array of size n,
and its populated with consecutive integers
from 1
to n, i.e. [1, 2...n-1, n] in random order.
Two integers are removed,
meaning zero is placed in their places.
Give O (n) efficient algorithm
to find them WITHOUT using extra space?

I expect that any solution would require at least O(1) extra
space.

/* BEGIN extra_space.c */

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE 20
#define FIRST_ZERO 3
#define SECOND_ZERO 17
#define LU_RAND(S) ((S) * 69069 + 362437)
#define LU_RAND_SEED 123456789LU

void all_different(long unsigned *array, long unsigned n,
long unsigned seed);
void place_zeros(long unsigned *array, long unsigned n,
long unsigned first, long unsigned second);
void find_numbers(long unsigned *array, long unsigned n,
long unsigned *number, long unsigned *scratch);

int main(void)
{
long unsigned *array, *extra_space, n, number[2];

array = malloc(ARRAY_SIZE * sizeof *array);
if (array == NULL) {
fputs("malloc failure_1\n", stderr);
exit(EXIT_FAILURE);
}
extra_space = malloc(ARRAY_SIZE * sizeof *extra_space);
if (extra_space == NULL) {
fputs("malloc failure_2\n", stderr);
exit(EXIT_FAILURE);
}
all_different(array, ARRAY_SIZE, LU_RAND_SEED);
place_zeros(array, ARRAY_SIZE, FIRST_ZERO, SECOND_ZERO);
find_numbers(array, ARRAY_SIZE, number, extra_space);
free(extra_space);
for (n = 0; n != ARRAY_SIZE; ++n) {
printf("%lu\n", array[n]);
}
free(array);
printf("\n%lu %lu\n", number[0], number[1]);
return 0;
}

void find_numbers(long unsigned *array, long unsigned n,
long unsigned *number, long unsigned *scratch)
{
long unsigned count, index;

for (count = 0; count != n; ++count) {
scratch[count] = 0;
}
for (count = 0; count != n; ++count) {
if (array[count] != 0) {
scratch[array[count] - 1] = array[count];
}
}
for (index = count = 0; count != n; ++count) {
if (scratch[count] == 0) {
number[index++] = count + 1;
if (index == 2) {
break;
}
}
}
}

void place_zeros(long unsigned *array, long unsigned n,
long unsigned first, long unsigned second)
{
while (n-- != 0) {
if (array[n] == first || array[n] == second) {
array[n] = 0;
}
}
}

void all_different(long unsigned *array,
long unsigned n, long unsigned seed)
{
long unsigned i, r;

array[0] = 1;
for (i = 1; n > i; ++i) {
seed = LU_RAND(seed);
r = seed % (i + 1);
array = 0;
array = array[r];
array[r] = i + 1;
}
}

/* END extra_space.c */

 

[CBFalconer]

.... snip ..

Why do people keep replying to this idiot (puzzlecracker)? He
constantly posts off-topic threads, most of the rest is this type
of stupid "here figure this out" crap. When he does, he usually
refuses to use proper usenet etiquette and quote messages properly,
even though he's been instructed several times on how to that.
I'm plonking him, I'm just plain old tired of his behavior.

He's only hanging on here by a thread, because I thought I saw a
sign of reformation (a quote) a while ago.