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 :) .
Printable View
I will help a bit :)
What does this line do?
Code:lastVal=arrSeries[MAXVALUE];
Of course :)Quote:
Originally Posted by Debojyoti Das
You don't need to use a divide and conquer strategy here.Quote:
Originally Posted by 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:
Please enter 10 numbers.1
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.
Everybody has gone out of bounds ;) The important thing is that you fixed it, doesn't that feel great? :D
Good that you noticed the out of bounds access. Now, test your program with input:
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.Code:2
2
2
2
2
2
2
2
2
1
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:
Please enter 10 numbers.2
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.
But all that you are doing is replacing the garbage values with other garbage values.Quote:
Originally Posted by Debojyoti Das
That is only because you did not recognise that j + 1 is your reduced range's length.Quote:
Originally Posted by Debojyoti Das
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?Quote:
Originally Posted by Debojyoti Das
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;
}
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?