# Array Comparison and Modification

Show 80 post(s) from this thread on one page
Page 4 of 5 First 12345 Last
• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by laserlight
Okay, looking through this thread again, I see that other than your solution in post #19, which is admittedly more complicated than necessary, your solutions use an extra array when this can be done in-place. Why not try for a simpler in-place solution? It seems that you are close. You could re-read Adak's post #9, but note that "move all the higher numbers, down by one index" is an unnecessary step.

An in-place solution would surely reduce space complexity and as this would be a divide and conquer method, time complexity may improve. A good proposition indeed.Working out now :) .
• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by std10093
It seems ok :)

I would throw away k and use i in lines 42 to 49.
Like this
Code:

``` i = MAXVALUE;  while(i!=0)     {         if(newArray[i]==lastVal)         {             readCounter--;         }         i--;     }```
Another thing I would change is this
Code:

```while(i!=MAXVALUE)     {         newArray[i]=lastVal;         i++;     }```
to this (since we know how many loops are going to be done, we should use for loop. Using while loop is not wrong. )
Code:

```for( i = 0 ; i < MAXVALUE i++) {         newArray[i]=lastVal; }```
As a result, I would change also the part that I used i instead of k.
Code:

``` i = MAXVALUE;  while(i!=0)     {         if(newArray[i]==lastVal)         {             readCounter--;         }         i--;     }```
to this
Code:

``` i = MAXVALUE;  for( i = MAXVALUE ; i > 0 ; i--) {         if(newArray[i]==lastVal)         {             readCounter--;         } }```

I run it without changing your code and I got
Code:

```Macintosh-c8bcc88e5669-9:~ usi\$ ./px Please enter 10 numbers. 1 1 1 1 14 5 6 7 3 4 1  14  5  6  7  3  4  1693429850  The number of steps: 6. The new array length is 8.```
Also when you print the new array length put a newline to the printf ;)

Wow ! I will change and try to fix the bug :) .

EDIT:
Quote:

for( i = 0 ; i < MAXVALUE:)i++)

{ newArray[i]=lastVal; }
You missed a semicolon there :) .
• 12-22-2012
std10093
I will help a bit :)
What does this line do?
Code:

`lastVal=arrSeries[MAXVALUE];`
• 12-22-2012
laserlight
Quote:

Originally Posted by Debojyoti Das
An in-place solution would surely reduce space complexity

Of course :)

Quote:

Originally Posted by Debojyoti Das
and as this would be a divide and conquer method

You don't need to use a divide and conquer strategy here.
• 12-22-2012
Debojyoti Das
Edited. Returns correct results for me :). Added a newline character as well :) .

Code:

```#include <stdio.h>#include <stdlib.h> #define MAXVALUE 10 int compact (int[], int); int main() {     int arrSeries[MAXVALUE], i=0, newArrayLength;     int arrLength = MAXVALUE;     printf("Please enter %d numbers.\n", MAXVALUE);     while(i != MAXVALUE)     {         scanf("%d", &arrSeries[i]);         i++;     }     newArrayLength=compact(arrSeries, arrLength);     printf("The new array length is %d.\n", newArrayLength);     getchar();     return 0; } int compact(int arrSeries[], int arrLength) {     int i=0, j= 0, counter=0, newArray[MAXVALUE], lastVal, readCounter=MAXVALUE;     lastVal=arrSeries[(MAXVALUE-1)];     lastVal++;     for( i = 0 ; i < MAXVALUE; i++)         {             newArray[i]=lastVal;         }     newArray[0]=arrSeries[0];     for(i = 0; i != arrLength; i++)         {             if(newArray[j] != arrSeries[i])             {                 newArray[++j] = arrSeries[i];             }         }     i=MAXVALUE;     for( i = MAXVALUE ; i > 0 ; i--)         {             if(newArray[i]==lastVal)             {                 readCounter--;             }         }     while(counter <= readCounter)         {             printf("%d  ", newArray[counter]);             counter++;         }     printf("\nThe number of steps: %d.\n", j);     return ++readCounter; }```

Quote:

1
1
1
14
5
6
7
3
4
1 14 5 6 7 3 4
The number of steps: 6.
The new array length is 7.
Process returned 0 (0x0) execution time : 21.715 s
Press any key to continue.

• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by std10093
I will help a bit :)
What does this line do?
Code:

`lastVal=arrSeries[MAXVALUE];`

Out of bounds :(. Silly me.
• 12-22-2012
std10093
Everybody has gone out of bounds ;) The important thing is that you fixed it, doesn't that feel great? :D
• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by laserlight
You don't need to use a divide and conquer strategy here.

Not exactly divide and conquer but my approach will be to divide the partition into repeating sets and then put one instance for the same and keep the non-repeating sets as is. I think it might be faster than before.
• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by std10093
Everybody has gone out of bounds ;) The important thing is that you fixed it, doesn't that feel great? :D

It surely does :) ! Thanks :) .
• 12-22-2012
laserlight
Good that you noticed the out of bounds access. Now, test your program with input:
Code:

```2 2 2 2 2 2 2 2 2 1```
Frankly, I still don't understand why you are trying to designate a particular invalid value to pre-fill the extra array when you don't need to.

EDIT:
Oh wait, you're just printing the array based on the reduced range, which means that the output should be fine... but it also means that the whole lastVal business is utterly pointless.
• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by laserlight
Good that you noticed the out of bounds access. Now, test your program with input:
Code:

```2 2 2 2 2 2 2 2 2 1```
Frankly, I still don't understand why you are trying to designate a particular invalid value to pre-fill the extra array when you don't need to.

EDIT:
Oh wait, you're just printing the array based on the reduced range, which means that the output should be fine... but it also means that the whole lastVal business is utterly pointless.

Just to do replace the garbage values I guess. And in my version of the code I get the reduced range based on my lastVal thingy. I do recognize that other workarounds are possible and I will try another way in the method you cited for getting the reduced range.
As off the data set you presented, it works perfectly for me:
Quote:

2
2
2
2
2
2
2
2
1
2 1
The number of steps: 1.
The new array length is 2.

Process returned 0 (0x0) execution time : 5.382 s
Press any key to continue.

• 12-22-2012
laserlight
Quote:

Originally Posted by Debojyoti Das
Just to do replace the garbage values I guess.

But all that you are doing is replacing the garbage values with other garbage values.

Quote:

Originally Posted by Debojyoti Das
And in my version of the code I get the reduced range based on my lastVal thingy.

That is only because you did not recognise that j + 1 is your reduced range's length.

Quote:

Originally Posted by Debojyoti Das
As off the data set you presented, it works perfectly for me:

Print the entire new array, including the garbage values. If you didn't know the reduced range's length, how can you tell that the 2s that come after the 1 are garbage? But since you know the reduced range's length, what does it matter what those values are?
• 12-22-2012
Debojyoti Das
Quote:

Originally Posted by laserlight
But all that you are doing is replacing the garbage values with other garbage values.

That is only because you did not recognise that j + 1 is your reduced range's length.

Print the entire new array, including the garbage values. If you didn't know the reduced range's length, how can you tell that the 2s that come after the 1 are garbage? But since you know the reduced range's length, what does it matter what those values are?

Whoa..now I recognize it. Thanks for the take :) .
• 12-22-2012
laserlight
You're welcome :)

Now, as you figure out a simpler in-place algorithm, I'd like to return to the idea that functions should do one thing and do it well. For example, this was the program I wrote to test:
Code:

```#include <stdio.h> size_t read_numbers(int numbers[], int max_size) {     size_t i = 0;     printf("Please enter up to %d integers (trigger EOF to stop early).\n", max_size);     while (i < max_size && scanf("%d", &numbers[i]) == 1)     {         ++i;     }     return i; } void print_numbers(const int numbers[], size_t size) {     size_t i;     printf(">>> ");     for (i = 0; i < size; ++i)     {         printf("%d ", numbers[i]);     }     printf("<<<\n"); } size_t compact(int numbers[], size_t size) {     size_t i, j;     if (size <= 1)     {         return size;     }     /* omitted for instructional purposes */ } int main(void) {     int numbers[10];     size_t size = read_numbers(numbers, sizeof(numbers) / sizeof(numbers[0]));     size = compact(numbers, size);     print_numbers(numbers, size);     return 0; }```
• 12-22-2012
R.Stiltskin
Still working on this, I see. I was hoping that by the time you finished implementing the step-counting you would have realized how simply (and efficiently) you could complete the assignment with only a minor modification to your original program. Does this give you a hint?
Show 80 post(s) from this thread on one page
Page 4 of 5 First 12345 Last