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?
41  2177 
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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" <ir*********@gmail.com> writes: 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?
Use a bit vector, requiring O(n) time and space.
--
"If I've told you once, I've told you LLONG_MAX times not to
exaggerate."
--Jack Klein
>bit vector
No extra space!
"puzzlecracker" <ir*********@gmail.com> writes: bit vector
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.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
"puzzlecracker" <ir*********@gmail.com> writes: bit vector
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?
--
Ben Pfaff
email: bl*@cs.stanford.edu
web: http://benpfaff.org
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
"puzzlecracker" <ir*********@gmail.com> writes: 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?
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
latter, sure you can declare variables. Sorry for lack of formality,
next time I'll be more formal in providing the description... good luck!
"puzzlecracker" <ir*********@gmail.com> writes: 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.
--
"A lesson for us all: Even in trivia there are traps."
--Eric Sosman
"puzzlecracker" <ir*********@gmail.com> writes: 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:
] "puzzlecracker" <ir*********@gmail.com> writes:
] > 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.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
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
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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?
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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
Allan Bruce wrote:
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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"
--
pete
Allan Bruce wrote: "puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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
"Allan Bruce" <ab****@TAKEMEAWAY.csd.abdn.ac.uk> writes: "puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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?
I think the intent is to determine which of the values from 1 to n
have been replaced by zeros, not their positions in the array (though
the wording does imply the latter).
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11**********************@c13g2000cwb.googlegr oups.com...
Allan Bruce wrote: "puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11**********************@c13g2000cwb.googlegr oups.com...
Allan Bruce wrote: "puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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?
Keith Thompson wrote: "puzzlecracker" <ir*********@gmail.com> writes: 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.
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
puzzlecracker wrote: 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 wrote: puzzlecracker wrote:
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
Ben Pfaff wrote:
"puzzlecracker" <ir*********@gmail.com> writes:
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[i] = 0;
array[i] = array[r];
array[r] = i + 1;
}
}
/* END extra_space.c */
--
pete
Default User wrote:
.... 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.
--
"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
"Default User" <de***********@yahoo.com> writes:
[...] Why do people keep replying to this idiot (puzzlecracker)?
I've seen rare cases of apparent trolls actually learning how to post
properly. I'm not optimistic that puzzlecracker will be one of these
rare cases, but I did actually see him post a followup with a proper
quotation from the prevous article.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
puzzlecracker <ir*********@gmail.com> scribbled the following: 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?
You need a separate array for which integers you've seen. Iterate
through your original array, marking non-zero elements as seen in your
separate array. Then iterate through your separate array, and point out
any values that have not been marked as seen.
The rest of your homework, i.e. writing this out in actual C code, is
left for you.
--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"A bee could, in effect, gather its junk. Llamas (no poor quadripeds) tune
and vow excitedly zooming."
- JIPsoft
U know sum from 1 to n ==> say it's S
Sum the array elements ===> say this is S1
Sum of two missing numbers (say a and b ) = (S-S1), i.e., a+b = S-S1 = K,
say.
Now assume value for a (with in n/2) and go on searching in the array, if
the assumed value is not found in the array, done, a = assumed value and b =
K - assumed value .
If not, ie., if the assumed value is found in the array both assumed value
and K - assumed values are aleady in the array, and the search order
reduces.
Go on storing this info ( about already existing numbers, so that u don't
search them again).
U'll find the solution very soon....
"Harshan" <ha***********@in.bosch.com> wrote in message
news:cs**********@ns2.fe.internet.bosch.com... 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
"puzzlecracker" <ir*********@gmail.com> wrote in message
news:11*********************@f14g2000cwb.googlegro ups.com... 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?
Ok, you didn't explain the limits on your "integers", so I am going to
go ahead and do the cheaters algorithm. Compute each of the following
(which are each O(n)):
1. s = sum of numbers given.
2. p = product of numbers given.
3. t = n!
Then if the two numbers are a and b, we know that:
1. (a + b) = n*(n+1)/2 - s
2. (a*b) = t / p
Now we can see that:
(x - a) * (x - b) = x^2 - (a + b) * x + (a * b)
However this quadratic clearly has the roots a and b. So solving for
the two roots using the classical quadratic formula will yield the two
solutions a and b. QED.
Ok, but all this requires a bignum library and n! is actually a very
large and slow number to compute (that requires roughly O(n*log(n))
memory).
So lets say we are stuck using C, Pascal or some other fixed integer
sized language, and we don't want to cheat. Then what we can do is
find the smallest prime k, which is greater than n^2 and work out:
1. t = n! (mod k)
2. p = product of inverses numbers given (mod k)
Then work out (t * p) (mod k) and it will be exactly the product a and
b. This still requires a double-wide integer math library (which
includes the ability to take square roots for the quadratic solve), but
the time and space requirements for such a thing is still O(1).
On a typical 32 bit machine, assuming n < INT_MAX , we can use the
usually available 64 bit integer support to do this. The only
complication is that working out the inverses (mod k) can be a big pain
in the ass (but it is still O(1), so I am set).
If you are unsatisfied with this, there is likely a way to solve it
analytically by computing a + b and a^2 + b^2, (I am too lazy to try to
go through the details) but this technically requires *triple*-wide
integer support.
--
Paul Hsieh http://www.pobox.com/~qed/ http://bstring.sf.net/ we******@gmail.com wrote:
Ok, you didn't explain the limits on your "integers", so I am going to
go ahead and do the cheaters algorithm. Compute each of the following
(which are each O(n)):
1. s = sum of numbers given.
2. p = product of numbers given.
3. t = n!
Then if the two numbers are a and b, we know that:
1. (a + b) = n*(n+1)/2 - s
2. (a*b) = t / p
Now we can see that:
(x - a) * (x - b) = x^2 - (a + b) * x + (a * b)
However this quadratic clearly has the roots a and b. So solving for
the two roots using the classical quadratic formula will yield the two
solutions a and b. QED.
Ok, but all this requires a bignum library and n! is actually a very
large and slow number to compute (that requires roughly O(n*log(n))
memory).
It's OK if the array is small.
/* BEGIN no_extra_space.c */
#include <stdio.h>
#define NMEMB 10
#define FIRST_ZERO 3
#define SECOND_ZERO 8
#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 irt(long unsigned n);
int main(void)
{
long unsigned array[NMEMB], number[2], n;
all_different(array, NMEMB, LU_RAND_SEED);
place_zeros(array, NMEMB, FIRST_ZERO, SECOND_ZERO);
find_numbers(array, NMEMB, number);
for (n = 0; n != NMEMB; ++n) {
printf("%lu\n", array[n]); }
printf("\n%lu %lu\n", number[0], number[1]);
return 0;
}
void find_numbers(long unsigned *array, long unsigned n,
long unsigned *number)
{
const size_t count = n;
long unsigned n_factorial, n_sum;
long unsigned array_factorial, array_sum;
long unsigned product, sum;
for (n_factorial = 1; n != 0; --n) {
n_factorial *= n;
}
n = count;
for (n_sum = 0; n != 0; --n) {
n_sum += n;
}
array_factorial = 1;
n = count;
while (n-- != 0) {
if (array[n] != 0) {
array_factorial *= array[n];
}
}
n = count;
array_sum = 0;
while (n-- != 0) {
array_sum += array[n];
}
product = n_factorial / array_factorial;
sum = n_sum - array_sum;
number[0] = (sum - irt(sum * sum - 4 * product)) / 2;
number[1] = sum - number[0];
}
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[i] = 0;
array[i] = array[r];
array[r] = i + 1;
}
}
long unsigned irt(long unsigned n)
{
long unsigned a, b;
a = n;
for (b = (1 == n) + n >> 1; n > b; b = a / n + n >> 1) {
n = b;
}
return n;
}
/* END no_extra_space.c */
--
pete
On Thu, 20 Jan 2005 19:30:52 +0000, pete wrote: Ben Pfaff wrote:
"puzzlecracker" <ir*********@gmail.com> writes:
> 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.
....
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;
}
}
}
}
You can do this inplace in array, i.e. without needing the extra scratch
array:
void find_numbers_inplace(long unsigned *array, long unsigned n,
long unsigned *number)
{
long unsigned count, index;
for (count = 0; count != n; count++) {
long unsigned tmp;
while ((tmp = array[count]) != 0 && count != tmp-1) {
array[count] = array[tmp-1];
array[tmp-1] = tmp;
}
}
for (index = count = 0; count != n; ++count) {
if (array[count] == 0) {
number[index++] = count + 1;
if (index == 2) {
break;
}
}
}
}
And, yes, this is an O(n) algorithm despite appearances (i.e. the nested
loops).
Lawrence
On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
wrote: 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?
easy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#define R return
#define W while
#define P printf
#define F for
void stampa_vals(unsigned* a, unsigned num)
{unsigned n, n2, i, s, s2, w, g, g2, r;
double rr;
n=(num*(num+1))/2; n2=(n*(2*num+1))/3;
// n=1+2+3+4+..+(num-1) n2=1^2+2^2+..+(num-1)^2
F(i=0, s=0, s2=0;i<num; ++i) // g=n -s = x1 +x2
{s+=a[i]; s2+=a[i]*a[i];} // w=n2-s2 = x1^2+x2^2
// x1=g-x2 => (g-x2)^2+x2^2=w
// g^2+x2^2-2gx2+x2^2-w=0 => 2x2^2-2gx2+g^2-w=0
// x2= (g+-sqrt(g^2 - 2 (g^2-w)))/2
// x2= (g+-sqrt(2w - g^2)/2
g=n-s; w=n2-s2; g2=g*g;
r= 2*w - g2; r=sqrt((double)r);
if(g==r) P("La soluzione e': %u\n", (g+r)/2);
else P("Le soluzioni sono: %u, %u\n", (g-r)/2, (g+r)/2);
}
void zera2(unsigned* a, unsigned num)
{unsigned i, j;
if(num<=1 || a==0) R;
i=rand()%num; j=rand()%num;
a[i]=0; a[j]=0;
}
void rimescola(unsigned* a, unsigned num)
{unsigned i, j, k, temp;
if(num<=1 || a==0) R;
for(i=0; i<num+10; ++i)
{ j=(unsigned)rand()%num; k=(unsigned)rand()%num;
if(j>num || k>num) {P("\a\n"); exit(0); }
if(j==k) continue;
temp=a[k]; a[k]=a[j]; a[j]=temp;
}
}
void print_a(unsigned* a, unsigned num)
{unsigned i;
F(i=0;i<num; ++i)
P("%u ", a[i]);
P(" ");
}
int main(void)
{unsigned char num;
unsigned *a, i;
srand(time(0));
label:
num=(unsigned char)rand();
num=num%30;
if(num<2) goto label;
a=malloc(num*(1 + sizeof *a));
F(i=0; i<num; ++i)
a[i]=i+1;
print_a(a, num); P("\n");
rimescola(a, num);
print_a(a, num); P("\n");
zera2(a, num);
print_a(a, num); P("\n");
stampa_vals(a,num);
free(a);
P("\n");
R 0;
} /* main, endswith */
RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following: On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
wrote:
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?
easy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#define R return
#define W while
#define P printf
#define F for
You have been told over and over again to stop using these ridiculous
obfuscated macros. Why do you persist on using them? Are you hell-bent
on making your code unreadable? Do you fancy yourself as some weirdo
guru who gets things working but no one knows how? Did you fail to get
all the jokes about "job security", thinking it was all true? Or are you
simply a troll?
--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"Holy Banana of this, Sacred Coconut of that, Magic Axolotl of the other."
- Guardian in "Jinxter"
On Sat, 29 Jan 2005 18:58:23 GMT, RoSsIaCrIiLoIA <n@esiste.ee> wrote: On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
wrote:
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?
easy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <time.h>
#include <math.h>
#define R return
#define W while
#define P printf
#define F for
On 29 Jan 2005 20:32, Joona I Palaste <pa*****@cc.helsinki.fi> wrote: RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following: On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
wrote: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?
easy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#define R return
#define W while
#define P printf
#define F for
You have been told over and over again to stop using these ridiculous
obfuscated macros. Why do you persist on using them? Are you hell-bent
on making your code unreadable? Do you fancy yourself as some weirdo
guru who gets things working but no one knows how? Did you fail to get
all the jokes about "job security", thinking it was all true? Or are you
simply a troll?
I've missed a macro: #define G goto
I think that people think that goto is wrong are poor incompetents lot
more than me. Am I a Troll? :)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <time.h>
#define R return
#define W while
#define P printf
#define F for
#define G goto
void stampa_vals(unsigned* a, unsigned num)
{unsigned n, n2, s, s2, w, g, r;
/*-----------------------------------------*/
assert( a!=0 && num!=0 );
n=(num*(num+1))/2; n2=(n*(2*num+1))/3;
// n=1+2+3+4+..+(num-1) n2=1^2+2^2+..+(num-1)^2
w=0; s=0; s2=0;
la: s+=a[w]; s2+=a[w]*a[w]; if(++w<num) G la;
// w=n2-s2 = x1^2+x2^2
// g=n -s = x1 +x2
// x1=g-x2 => (g-x2)^2+x2^2=w
// g^2+x2^2-2gx2+x2^2-w=0 => 2x2^2-2gx2+g^2-w=0
// x2= (g+-sqrt(g^2 - 2(g^2-w)))/2
// x2= (g+-sqrt(2w - g^2)/2
g= n-s; w=n2-s2;
if(g==0){P("Tutti i numeri sono presenti\n"); R;}
r= 2*w - g*g; r=sqrt((double)r);
if(g==r) P("La soluzione e': %u\n", (g+r)/2);
else P("Le soluzioni sono: %u, %u\n", (g-r)/2, (g+r)/2);
}
void zera2(unsigned* a, unsigned num)
{unsigned i, j;
assert(a!=0 && num!=0);
if(num<=1) R;
i=rand()%num; j=rand()%num;
a[i]=0; a[j]=0;
}
void rimescola(unsigned* a, unsigned num)
{unsigned i, j, k, temp;
assert(a!=0 && num!=0);
if(num<=1) R;
i=0;
la:
j=rand()%num; k=rand()%num;
if(j==k) G la;
temp=a[k]; a[k]=a[j]; a[j]=temp;
if(++i<num+10) G la;
}
void print_a(unsigned* a, unsigned num)
{unsigned i;
/*---------------------*/
assert(a!=0 && num!=0);
i=0;
la: P("%u ", a[i]);if(++i<num) G la;
P(" ");
}
int main(void)
{unsigned char num;
unsigned *a, i;
/*-----------------------------*/
srand(time(0));
l0: num=rand(); num=num%30; if(num<2) G l0;
a=malloc((num+1)*(sizeof *a));
if(a==0) R 0;
i=0;
la: a[i]=i+1; if(++i<num) G la;
print_a(a, num); P("\n");
rimescola(a, num);
print_a(a, num); P("\n");
zera2(a, num);
print_a(a, num); P("\n");
stampa_vals(a,num);
free(a);
P("\n");
R 0;
} /* main, endswith */
RoSsIaCrIiLoIA wrote: On 29 Jan 2005 20:32, Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following:
On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
wrote:
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?
easy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#define R return
#define W while
#define P printf
#define F for
You have been told over and over again to stop using these ridiculous
obfuscated macros. Why do you persist on using them? Are you hell-bent
on making your code unreadable? Do you fancy yourself as some weirdo
guru who gets things working but no one knows how? Did you fail to get
all the jokes about "job security", thinking it was all true? Or are you
simply a troll?
I've missed a macro: #define G goto
I think that people think that goto is wrong are poor incompetents lot
more than me. Am I a Troll? :)
The latter does not make you a troll.
The obfuscated macros would get you warned once or twice and then fired
in a company where I had the say.
Your way of mixing your first and second name at least may be playful
but does you no credit.
The look of your code is a little crowded; I like more spacing and put
only seldom two assignments on the same line.
Cheers
Michael
[snip: not very readable code]
--
E-Mail: Mine is an /at/ gmx /dot/ de address.
Michael Mair wrote: RoSsIaCrIiLoIA wrote: Joona I Palaste <pa*****@cc.helsinki.fi> wrote: RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following:
"puzzlecracker" <ir*********@gmail.com> wrote:
> Given an array of size n and populated with consecutive
.... snip unimportant ...
#define R return
#define W while
#define P printf
#define F for
You have been told over and over again to stop using these
ridiculous obfuscated macros. Why do you persist on using them?
.... snip ...
more than me. Am I a Troll? :)
The latter does not make you a troll.
He has been warned and warned. Many of us have him in the PLONK
bin, and wouldn't be bothered by his reappearance if you and Joona
didn't insist on quoting him. Don't feed the trolls.
--
"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
CBFalconer <cb********@yahoo.com> scribbled the following: Michael Mair wrote: RoSsIaCrIiLoIA wrote: Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following:
> "puzzlecracker" <ir*********@gmail.com> wrote:
>
>> Given an array of size n and populated with consecutive
... snip unimportant ... >>>
>>>#define R return
>>>#define W while
>>>#define P printf
>>>#define F for
>>
>> You have been told over and over again to stop using these
>> ridiculous obfuscated macros. Why do you persist on using them?
... snip ...
more than me. Am I a Troll? :)
The latter does not make you a troll.
He has been warned and warned. Many of us have him in the PLONK
bin, and wouldn't be bothered by his reappearance if you and Joona
didn't insist on quoting him. Don't feed the trolls.
Sorry about that. Rossiacrilioa or whatever his name is escaped my
killfile when he changed e-mail addresses. I've now rekillfiled him,
this time by name rather than e-mail address.
--
/-- Joona Palaste (pa*****@cc.helsinki.fi) ------------- Finland --------\
\-------------------------------------------------------- rules! --------/
"I said 'play as you've never played before', not 'play as IF you've never
played before'!"
- Andy Capp
On Sun, 30 Jan 2005 22:08:03 +0100, Michael Mair
<Mi**********@invalid.invalid> wrote: RoSsIaCrIiLoIA wrote: On 29 Jan 2005 20:32, Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following:
On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
wrote:
>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?
easy
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#define R return
#define W while
#define P printf
#define F for
You have been told over and over again to stop using these ridiculous
obfuscated macros. Why do you persist on using them? Are you hell-bent
on making your code unreadable? Do you fancy yourself as some weirdo
guru who gets things working but no one knows how? Did you fail to get
all the jokes about "job security", thinking it was all true? Or are you
simply a troll?
I've missed a macro: #define G goto
I think that people think that goto is wrong are poor incompetents lot
more than me. Am I a Troll? :)
The latter does not make you a troll.
The obfuscated macros would get you warned once or twice and then fired
in a company where I had the say.
I'm a amateur programmer and so I have no one here (except my own
head) that says me what it is wrong and what is good (when I hear, I
decide what is right and what is wrong).
I think that if one programmer doesn't understand he must to use the
proper tool (a "indent" programme)(it would be easy and in a second he
is ok). If this doesn't help he have to study more. If some leader of
a company think otherwise he does errors and so all can happen in his
company.
Your way of mixing your first and second name at least may be playful
but does you no credit.
The look of your code is a little crowded; I like more spacing and put
only seldom two assignments on the same line.
Cheers
Michael
[snip: not very readable code]
RoSsIaCrIiLoIA <n@esiste.ee> writes:
[...] I'm a amateur programmer and so I have no one here (except my own
head) that says me what it is wrong and what is good (when I hear, I
decide what is right and what is wrong).
Fine, if you want to think that you're right and everyone else is
wrong, you're free to believe that. But your use of macros like
#define R return
#define W while
#define P printf
#define F for
makes your code more difficult to read, and it means that most of us
will not spend the extra time necessary to read it. Continue to use
them, and we'll continue to ignore you.
--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
"Richard Bos" <rl*@hoekstra-uitgeverij.nl> wrote in message
news:41***************@news.individual.net... RoSsIaCrIiLoIA <n@esiste.ee> wrote:
<Mi**********@invalid.invalid> wrote:>>RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following:
>>
>>>#define R return
>>>#define W while
>>>#define P printf
>>>#define F forThe obfuscated macros would get you warned once or twice and then
firedin a company where I had the say.
I'm a amateur programmer and so I have no one here (except my own
head) that says me what it is wrong and what is good (when I hear, I
decide what is right and what is wrong).
That's a load of bovine excrement. You have been told repeatedly
_here_, in this newsgroup, that those macros are losing in the extreme. And
yet you continue to use them. To, me this suggests one of three things:
either you are a troll, or you are an idiot, or you are a loser. Cut
the crap or take your pick of those three.
Many people come up with syntax that seems "natural" to them, and the
macro seems like the easiest / best way to "improve" the language. But
you always have to remember the you are writing C code for C programmers
and we all know C, not your little "conveniences". Once you have worked
with a few people who try to do that you understand that there is little
value in trying to "improve" C. Just write simple, straight-forward C
code and you'll be happier in the long run.
Or pick / write a new language and write code in that. There are always
editors that can be set up to put the word "return" when you type R and
a space. Learn them, if you are concerned with your typing speed or
proficiency.
--
Mabden
Michael Mair wrote:
RoSsIaCrIiLoIA wrote:
Am I a Troll? :)
The latter does not make you a troll.
The obfuscated macros would get you warned
once or twice and then fired in a company where I had the say.
He's been warned about writing that way for a couple of years. http://groups.google.co.uk/groups?se...mindspring.com
--
pete
Lawrence Kirby wrote:
On Thu, 20 Jan 2005 19:30:52 +0000, pete wrote:
Ben Pfaff wrote:
"puzzlecracker" <ir*********@gmail.com> writes:
> 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.
...
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;
}
}
}
}
You can do this inplace in array,
i.e. without needing the extra scratch array:
void find_numbers_inplace(long unsigned *array, long unsigned n,
long unsigned *number)
{
long unsigned count, index;
for (count = 0; count != n; count++) {
long unsigned tmp;
while ((tmp = array[count]) != 0 && count != tmp-1) {
array[count] = array[tmp-1];
array[tmp-1] = tmp;
}
}
for (index = count = 0; count != n; ++count) {
if (array[count] == 0) {
number[index++] = count + 1;
if (index == 2) {
break;
}
}
}
}
And, yes, this is an O(n) algorithm despite appearances
(i.e. the nested loops).
Nested loops ?!
One of the smart guys on comp.programming described
something which I consider to be the "right" solution.
void find_numbers(long unsigned *array, long unsigned n,
long unsigned *number)
{
const long unsigned count = n;
long unsigned array_sum, sum, half_sum;
for (array_sum = n = 0; n != count; ++n) {
array_sum += array[n];
}
sum = (count + 1) * count / 2 - array_sum;
half_sum = sum / 2;
for (array_sum = n = 0; n != count; ++n) {
if (half_sum >= array[n]) {
array_sum += array[n];
}
}
number[0] = (half_sum + 1) * half_sum / 2 - array_sum;
number[1] = sum - number[0];
}
--
pete
On Mon, 31 Jan 2005 19:01:00 GMT, RoSsIaCrIiLoIA <n@esiste.ee> wrote: On Sun, 30 Jan 2005 22:08:03 +0100, Michael Mair
<Mi**********@invalid.invalid> wrote:
RoSsIaCrIiLoIA wrote: On 29 Jan 2005 20:32, Joona I Palaste <pa*****@cc.helsinki.fi> wrote:
RoSsIaCrIiLoIA <n@esiste.ee> scribbled the following:
>On 19 Jan 2005 17:43:29 -0800, "puzzlecracker" <ir*********@gmail.com>
>wrote:
>
>>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?
>
>easy
>#include <stdio.h>
>#include <stdlib.h>
>#include <string.h>
>#include <assert.h>
>#include <math.h>
>#define R return
>#define W while
>#define P printf
>#define F for
You have been told over and over again to stop using these ridiculous
obfuscated macros. Why do you persist on using them? Are you hell-bent
on making your code unreadable? Do you fancy yourself as some weirdo
guru who gets things working but no one knows how? Did you fail to get
all the jokes about "job security", thinking it was all true? Or are you
simply a troll?
I've missed a macro: #define G goto
I think that people think that goto is wrong are poor incompetents lot
more than me. Am I a Troll? :)
The latter does not make you a troll.
The obfuscated macros would get you warned once or twice and then fired
in a company where I had the say.
I'm a amateur programmer and so I have no one here (except my own
head) that says me what it is wrong and what is good (when I hear, I
decide what is right and what is wrong).
In the way: if something goes well in the reality that is good and I
choice that This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Juha Haataja |
last post by:
I have been learning Python since April, and would like a
few comments from the experts on list processing.
I managed to implement a Python code for solving the
so-called Einstein's Riddle, see...
|
by: pythonchallenge |
last post by:
For the riddles' lovers among you, you are most invited to take part
in the Python Challenge, the first python programming riddle on the net.
You are invited to take part in it at:...
|
by: Sara Khalatbari |
last post by:
Hey guys!
Thanks for helping me find time&date.
Have you seen this?
This is the first programming riddle on the net with
20 levels!
http://www.pythonchallenge.com/
...
|
by: ImortalSorrow |
last post by:
Please I need urgent help with this program! Everything is working well except a part where i want to repeat the riddle if the answer isnt correct. here's the code..hope someone can help me!
...
|
by: Charles Arthur |
last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
|
by: ryjfgjl |
last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Hystou |
last post by:
There are some requirements for setting up RAID:
1. The motherboard and BIOS support RAID configuration.
2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
| |
