Array function help

Hello,

I am trying to find the right code for this question, I am having problem understanding it

changes’s job is to go through the array from beginning to end, counting how many times the data changes its direction between increasing and decreasing. For instance, if the data is increasing, then decreasing, then increasing, then decreasing, changes will return 3. That is,

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
unsigned changes(const unsigned a[], unsigned elements)
{
unsigned count = 0, tell=0;
for (unsigned index1 = 0; index1 < elements; index1++)
{
	tell = 1;
if (a[index1] < a[index1 + 1])
	tell = -1;
if (a[index1] > a[index1 + 1])
	tell = 0;
if (a[index1] == a[index1 + 1])
count++;
}
return count;
}


I know it looks bad but I need first to get it the idea of it
Ok, here are some immediate errors or ambiguities that I see:

1. In the FOR loop, the variable index1 has a range of 0->elements-1 inclusive. However, the segmentation fault (index array out of bounds) error would probably occur at lines 7, 9, and 11 (if the variable elements is the size of the array a) because you try to access a[index1+1] when this area in memory is not allocated. You are essentially accessing one past the last valid element in array a.

FIX: You could alter the FOR loop construct to look like
for (unsigned index1 = 0; index1 < elements-1; index1++)

2. You increment count each time a[index1] == a[index1+1]. In this algorithm, you only want to increment count when the data changes from increasing to decreasing or decreasing to increasing. When two contiguous elements are equal, there is technically no change in data direction. You did a good job of breaking the algorithm down into individual cases, however the logic is not yet complete.

The first case is the data was previously increasing, but it has changed direction and is now decreasing.
1
2
3
4
5
if (a[index1] > a[index1+1] && direction == "increasing")
{
    count++;
    direction = "decreasing";
}


The second case is the data was previously decreasing, but it has changed direction and is now increasing.
1
2
3
4
5
if (a[index1] < a[index1+1] && direction == "decreasing")
{
    count++;
    direction = "increasing";
}


The third case is the data is neither increasing or decreasing.
1
2
if (a[index1] == a[index1+1])
    //Do nothing! 


So you see, a key component you were missing was storing a direction variable and testing it in the IF statements.

There is another technicality to this problem and it concerns inputs where the first two or more elements are equal e.g. {5, 5, 5, 7, 9, 3, 2} because you must first initialize a direction (increasing or decreasing). There is a simple workaround of iterating until two elements are not equal and then initialize the direction variable and begin the algorithm. I have a correct algorithm implemented, however, I will let this all sink in before posting it. Its important to understand the idea like you said!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
unsigned changes(const unsigned a[], unsigned elements)
{
unsigned count = 0, dirc=1;
for (unsigned index1 = 0; index1 < elements - 1; index1++)
{

if (a[index1] < a[index1 + 1] && dirc == -1)
{
count++;
dirc = 1;
}

if (a[index1] > a[index1 + 1] && dirc == 1)
{
count++;
dirc = -1;
}

//if (a[index1] == a[index1 + 1]);

}

return count;
}


I still don't know what is missing in the last IF statement
Last edited on
Getting there!

Watch your variable types, you try to assign a negative value to dirc on line 16 which is impossible because the type of dirc is unsigned. In the below code, for simplicity just use a boolean value denoting either increasing->true or decreasing->false.

When coded correctly, there is no third IF statement because when two contiguous elements are equal, you do not need to change direction, instead you keep saving the direction for later in the sequence when either a[index1] > a[index1+1] or a[index1] < a[index1+1].

Your solution is very close to being correct, there are still issues however. First, you simply initialize dirc=1, however, this is incorrect if the first two elements of a are e.g. {5, 3, ....}. You initialized it as increasing, but in reality it is decreasing. Heres the fix, it requires a couple lines before your FOR loop:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
unsigned changes(const unsigned a[], unsigned elements)
{
    unsigned count = 0, start = 0;
    
    //step through the beginning of the array while a[start] == a[start+1]
    //essentially ignore all beginning elements that are equal because they have
   // no direction.
    while (start+1 < elements && a[start] == a[start+1]) start++;

    //when the loop is finally finished ignoring all beginning 
    //equal elements, NOW assign a direction
    //Initialize increasing boolean, saves direction
    bool increasing = a[start] < a[start+1]; 
    

    //Now begin pass through the array because direction correctly initialized.
    for (unsigned index1 = start+1; index1 < elements-1; index1++)
    {
         if (a[index1] < a[index1+1] && !increasing)
         {
             count++;
             increasing = !increasing; //flip direction from increasing to decreasing 
         }
         if (a[index1] > a[index1+1] && increasing)
         {
              count++;
              increasing = !increasing;
          }
    }
    return count;
    
}

Let me know what you don't understand, this is a great problem that emphasizes logical thinking and also has many opportunities for expanding syntactical knowledge of C++.
Last edited on
I edited the code and figured out that I cannot put the els++ inside the FOR loop and I don't know why please tell me?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
unsigned changes(const unsigned a[], unsigned elements)
{

unsigned count = 0;
unsigned els;

for ( els=0; els + 1 < elements && a[els] == a[els + 1];) els++;
{
bool inc = a[els] < a[els + 1];

for (unsigned index1 = els+1; index1 < elements - 1; index1++)
{

if (a[index1] < a[index1 + 1] && !inc)
{
count++;
inc = !inc;
}

if (a[index1] > a[index1 + 1] && inc)
{
count++;
inc = !inc;
}

}
}

return count;
}
Last edited on
Try removing the unnecessary braces at lines 8 and 26. Then move the els++ back into the FOR loop. So the loop will look like this:
 
for (els = 0; els + 1 < elements && a[els] == a[els+1]; els++);


Those braces should not have been there, post any error messages you get if these changes don't work.

Also, please use indentation! Style is just as important as function!
Last edited on
it worked this way, I went through this problem on a paper and it now make sense to me but I am wondering if there is nicer and shorter way of doing this

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
unsigned changes(const unsigned a[], unsigned elements)
{

unsigned count = 0;
unsigned els;

for (els = 0; els + 1 < elements && a[els] == a[els + 1];)
	els++;
bool inc = a[els] < a[els + 1];
		for (unsigned index1 = els+1; index1 < elements - 1; index1++)
		{

	if (a[index1] < a[index1 + 1] && !inc)
		{
		count++;
		inc = !inc;
		}

	if (a[index1] > a[index1 + 1] && inc)
		{
		count++;
		inc = !inc;
		}

		}

		return count;
		}
Last edited on
Note:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
unsigned els;
for ( els = 0; els + 1 < elements && a[els] == a[els + 1]; )
  ++els;
// is same as
unsigned els;
for ( els = 0; els + 1 < elements && a[els] == a[els + 1]; )
 {
  ++els;
 }
// is same as
unsigned els;
for ( els = 0; els + 1 < elements && a[els] == a[els + 1]; ++els )
 {
 }
// is same as
unsigned els;
for ( els = 0; els + 1 < elements && a[els] == a[els + 1]; ++els )
 ;
// is same as
unsigned els = 0;
while ( els + 1 < elements && a[els] == a[els + 1] )
 {
    ++els;
 }


I would personally start the code:
1
2
3
4
5
6
7
8
9
10
11
12
unsigned elt = 1;
while ( elt < elements && a[elt - 1] == a[elt] )
 {
    ++elt;
 }

if ( elt == elements ) return count;
bool inc = a[elt - 1] < a[elt];

for ( unsigned index1 = elt + 1; index1 < elements; ++index1 )
 {
   // ... 
Last edited on
so basically we start at first element in array and we compare it and test it
The only difference between your code and mine is that while we both look at two consecutive elements, you refer to them by the index of the first (els) and I by the second (elt). els+1===elt
1
2
3
4
// You:
els = 0;  a[els] == a[els + 1]
// Me:
elt = 1; a[elt - 1] == a[elt]

In other words I place the +1 or -1 in different points.


Note: Line 7; return 0, if whole array has equal values rather than compute bool from a[elements] (out-of-range error).
Topic archived. No new replies allowed.