[Sandals456]

Hello,

I am needing help with sorted arrays and the time complexity of O(n).

The user has to put in 20 integers in a sorted array and a target number in which the program will find all the possible pairs that will equal to the target number. The time complexity has to be in O(n).

I don't really know where to start and I looked online and haven't found anything to help.

The only thing I was able to do is allow the user to input the integers, but beyond that I'm stuck...

[tlhIn`toq]

"I don't know where to start" - This usually means you should go back to your instructor and admit you are this lost. Don't bluff your way through this course thinking that by chapter 10 it will all suddenly snap into place and become clear. It won't. Unlike history class where chapter 1 might be 17th century England and chapter 2 might be World War II, giving you a fresh start - Coding builds upon the lessons of the previous chapter. You have to use lesson 1 material to succeed in lesson 2. Chapter 10 builds upon and uses material from chapter 9. If you let your pride get in the way you will be too lost to recover and have wasted thousands of dollars in tuition.

[Sandals456]

tlhIn`toq, on 02 February 2013 - 03:40 PM, said:

"I don't know where to start" - This usually means you should go back to your instructor and admit you are this lost. Don't bluff your way through this course thinking that by chapter 10 it will all suddenly snap into place and become clear. It won't. Unlike history class where chapter 1 might be 17th century England and chapter 2 might be World War II, giving you a fresh start - Coding builds upon the lessons of the previous chapter. You have to use lesson 1 material to succeed in lesson 2. Chapter 10 builds upon and uses material from chapter 9. If you let your pride get in the way you will be too lost to recover and have wasted thousands of dollars in tuition.

I'm not looking for someone to do the homework, I have an idea on the steps I can take in order to solve the question, I just don't have a really big idea in putting it in code since I barely started C.

This is what I have so far which is just letting the user input the integers into the array:

#include<stdio.h>

int main()
{
        int main_array[20];/*this is calling out the array with 20 variables*/

        int input; /*calling out the variable "input" for the user inputting the integers*/


        printf("Please enter 20 integers in ascending order.\n");
        for(input=0; input<20; input++);/*for loop for the user to no exceed the 20 elements*/
        {
                printf("#%2d >", input+1);
                scanf("%d", &main_array[input]);
        }
        return 0;
}

[jimblumberg]

So what kind of sorting algorithms have you studied? Your next step is to sort the array.

Jim

[Sandals456]

I don't really understand the question, so far though we have went through linear and binary search.

[Adak]

You can't sort an array (or anything else) in O(N). That's impossible.

You can get the EFFECT of sorting in O(N), by using counting sort. The numbers will stay in their original order, but you can find the answer you want, and even print the numbers, just LIKE they were in sorted order.

All caused by the organization of the array and using it's index system.

For example, say you have an unsorted array (the numbers have been entered already), like this:

int num[5]. Which has values of: 2, 0, 8, 1, 5.

Now to counting sort them:

int index[8]={0} -- range must be large enough to handle the highest number

now

for(i=0;i<5; increment i)
   increment index[number];

The reason it's faster than The Flash, is that it's so simple. Increments in C can be done using the common C idiom: variable++, or in an array, array[index]++.

It's not really flexible - doesn't handle negative values, or non-integers, or very large numbers.

This post has been edited by Adak: 02 February 2013 - 05:40 PM

[ButchDean]

It's only O(n) if it's effectively already sorted, which defeats the purpose of sorting in the first place. You should try implementing the bubble sort which is easy and serves as a nice introduction for you.

This post has been edited by ButchDean: 02 February 2013 - 06:25 PM

[Sandals456]

ButchDean, on 02 February 2013 - 06:25 PM, said:

It's only O(n) if it's effectively already sorted, which defeats the purpose of sorting in the first place. You should try implementing the bubble sort which is easy and serves as a nice introduction for you.

Ok well the integers are already assumed sorted, so I don't have to worry about sorting the array because the user will put the integers in ascending order.

[Sandals456]

This is what I have so far...

#include<stdio.h>

int main()
{
        int main_array[20];
        int element1 = 0;
        int element2 = 1;
        int target_number;

        printf("Please enter 20 integers\n");
        scanf("%d\n",&main_array);

        printf("Now enter a target number:\n");
        scanf("%d\n", target number);

        while( element2<20)
        {
                if(main_array[element1]+main_array[element2]==target_number)
                {
                printf("Both  %d and %d add up to  %d", main_array[element1], main_array[element2], element1++, element2++);
                }
                else if(main_array[element1]+main_array[element2]!=target_number)
                printf("No pairs in the given array can be summed to the target value.")

                {

                }

        }
}

[Sandals456]

There are two errors on lines 22 and 24. I'm not sure what it is.

#include<stdio.h>

int main()
{
        int main_array[20];
        int element1 = 0;
        int element2 = 1;
        int target_number;

        printf("Please enter 20 integers\n");
        scanf("%d\n",&main_array);

        printf("Now enter a target number:\n");
        scanf("%d\n",&target_number);

        while( element2<20)
        {
                if(main_array[element1]+main_array[element2]==target_number)
                {
                printf("Both  %d and %d add up to  %d", main_array[element1], main_array[element2], element1++, element2++);
                }
                else if((main_array[element1]+main_array[element2])!=target_number), element1++, element2++;
                printf("No pairs in the given array can be summed to the target value.")
        }
return 0;
}

[ButchDean]

You need to tell us exactly what the errors are.

[Sandals456]

ButchDean, on 02 February 2013 - 10:02 PM, said:

You need to tell us exactly what the errors are.

Q2.c:22: error: expected expression before â,â token
Q2.c:24: error: expected â;â before â}â token

These are the errors, I'm not sure what they mean.

[Sandals456]

I am using SSH Secure Shell Client so I don't know if it would make a difference.

[Adak]

Sandals456, on 02 February 2013 - 10:22 PM, said:

I am using SSH Secure Shell Client so I don't know if it would make a difference.

SSH is not the problem.

First problem is with the scanf(). You can't scan a value into the name of an array - nor into the address of the array name. You need this, but for 20 ints, instead of 5:

   printf("Please enter 5 integers\n");
   for(i=0;i<5;i++) {        
        scanf("%d\n",&main_array[i]);
   }

The bigger problem is with the while loop logic - it won't do the job, and has increments to element1 and element2, added onto the end of the same line of code (which is illegal). You have to separate statements in C, with a semi-colon, whether they're on the same line, or not.

I didn't correct it because it's "le garbage" in French.

What you need is two for loops. One nested inside the other. You want this pattern of indices:

1&2, 1&3, 1&4, 1&5
2&3, 2&4, 2&5
3&4, 3&5,
4&5

Which will give you every pair of indices in an array of 5 integers (for example). Continue this pattern in the nested loops to whatever size you need.

Here's how it could be done, with an array of 5 numbers:

for(i=0;i<5-1;i++) {
   for(j=i+1;j<5;j++) {
      if array[i]+array[j]== targetNumber) {
          printf("Found a match! %d and %d\n",array[i],array[j]);
      }
   }
}

Which isn't an intuitive thing to work out, if you haven't seen a Substitution sort before (or spent a lot of time working it out by hand at the kitchen table).

[undefined behaviour]

Firstly, for(input=0; input<20; input++); // <--- See that semi-colon on the end, there, Sandals456? What does that mean? What happens if you remove it? Which book are you reading?

Suppose there are twenty pidgeon holes for twenty apartments and I ask you to deliver and count the mail sent to each apartment, how will you do that? I'd put the mail in the correct pidgeon hole as it's passed to me, and count the letters in each pidgeon hole at the end. Do you suppose it might be possible to adapt this algorithm to solve your problem?

Adak, on 02 February 2013 - 05:37 PM, said:

You can't sort an array (or anything else) in O(N). That's impossible.

I love it how this problem doesn't specify that the time complexity be a measurement of worst case, best case or average case. O(N) in this case describes the function as linear in terms of constant time complexity. Suppose you time the sorting function, and sleep for N years minus the duration of the sort. The function might now be predictably linear in terms of constant time complexity