Arrays and more ...

[Slavi]

Hey guys,
another one that I got stuck on(Although I passed 4000 points, soon to be on the leader board!:D) ... so here is the idea

I have an input array for example {1,2,3,4,5,6,7} and an int number for example 10; so what I have to do is return all combinations for which the sum of 2 numbers will be 10. such as {{3,7},{4,6}}.

The problems that I am facing is that I have to return a 2d array and I can't know its size until everything is checked. so I tried something simple just to get all into 1d array and then make sets out of that array. But problem again is the size of the 1d array. Here is what I have

public static int[] Puzzle(int[] numbers, int x) {
        int position=0;
        int[] a = new int[numbers.length];
        for (int i = 0; i<numbers.length/2; i++){
            for (int j=0;j<numbers.length;j++){
                if((numbers[j]+numbers[i])== x) {
                    a[position] = i;
                    position++;
                    a[position] = j;
                    position++;
                }
            }
        }
        return a;
    }

if my input is {512,1,3,5,3} and 4 , my 1d array has 1,2,1,4,0 then again the size is a bit too much and has to be redifined. I think a solution would be to make at this point new array of size position and move all from a to the new one and then copy it once again into 2d? Seems inefficient somehow

[JamesCherrill]

There's nothing to gain by messing about with a 1D array. You can start with an array of doublets (arrays with 2 members), and add solutions to that as you find them. If you overflow the size you will need to copy to as larger array, and at the end you will need to copy to a smaller array of exactly the right size.
ArrayList anybody???

[Slavi]

Can't use array list, the compiler won't let me to :( How would I reduce the size to a correct one? like if i have array[3] but i could add only 2 items, how can I shrink it?

if array[i]!=0 can tell me whether array element is occupied and get the count of that then make new array of that count?

[oussama_1]

You need to return all possible combinations, so you need a method that returns a multidimensional array. Ok let's start with the main method; we will create a sample array with the list and then the 2D array that calls the method:

    public static void main(String[] args) {
      int a[] = {1,2,3,4,5,6,7},b[][] = Puzzle(a, 10);

      // display results:
      for(int i = 0; i < b.length; i++){
      for(int j = 0; j < b[i].length; j++){
        System.out.print(b[i][j]+" ");}
    System.out.println();}
    }    

The puzzle method; since we don't know how many rows are going to be in the 2D array i'm going to use the same loop(of checking out the combinations) to determine the number of rows:

public static int[][] Puzzle(int[] numbers, int x) {
    //Check rows number:
    int rows = 0,a = 0;
    for (int i = 0; i<numbers.length;i++){
           for (int j = i; j<numbers.length;j++){
               if (numbers[i] +numbers[j]==x){
                   rows++;
               }
    }} 

    //Check for combinations:
    int [][]b = new int [rows][2];
    for (int i = 0; i<numbers.length;i++){
           for (int j = i; j<numbers.length;j++){
               if (numbers[i] +numbers[j]==x){
                b[a][0] = numbers[i];
                b[a][1] = numbers[j];
                a++;
    }} 
    }return b; 

Good Luck.

[Slavi]

Hey oussama, thanks for replying! Pretty much what I thought in my previous response :) Thanks for clearing tho, 1 thing though ... when I have the code as this

public static int[][] Puzzle(int[] numbers, int x) {

    int rows = 0,a = 0;
    for (int i = 0; i<numbers.length;i++){
           for (int j = i; j<numbers.length;j++){
               if (numbers[i] +numbers[j]==x){
                   rows++;
               }
    }} 

    int [][]b = new int [rows][2];
    for (int i = 0; i<numbers.length;i++){
           for (int j = i; j<numbers.length;j++){
               if (i!=j){
                   if(numbers[i]+numbers[j] == x){
                        b[a][0] = i;
                        b[a][1] = j;
                        a++;
                    }
    }} 
    }return b; 
    }

its slighty chnaged to ur version, if I need to find whether 2 numbers sum to 66 and the first number of the array is {33, i, i, i,i}, I get output that {0,0} is a correct anwswer, where i and j are pointing to the same element however I am trying to avoid that, I don't want to sum the same element. What I did was to add if(i!=j) but it doesnt seem to be workin, any clue why?

[Slavi]

Here take a look at this >.>

[oussama_1]

Ok in the inner loop, [j] should always be a one step ahead of [i]:

public static int[][] Puzzle(int[] numbers, int x) {

    int rows = 0,a = 0;
    for (int i = 0; i<numbers.length;i++){
           for (int j = 1;j>i && j<numbers.length;j++){
               if (numbers[i] +numbers[j]==x){
                   rows++;
               }
    }} 

    int [][]b = new int [rows][2];
    for (int i = 0; i<numbers.length;i++){
           for (int j = 1;j>i && j<numbers.length;j++){
                   if(numbers[i]+numbers[j] == x){
                        b[a][0] = i;
                        b[a][1] = j;
                        a++;
                    }
    }
    }return b; 
    }

[Slavi]

Nope, same output :(

[oussama_1]

Make sure it's the same code i posted, because there's no way you'll get a {0,0} in the output, or send me your final code and i'll take a look at it

[Slavi]

.

[oussama_1]

In the picture; line 7 change it to:

for (int j = 1;j>i && j<numbers.length;j++){

[Slavi]

Some success but not fully :D

Not sure why wouldnt it write out {1,2} now, the loop seems good enough also 1<2

[oussama_1]

Ok i get it now.

public static int[][] Puzzle(int[] numbers, int x) {

    int rows = 0,a = 0;
    for (int i = 0; i<numbers.length;i++){
           for (int j = 1;j>=i && j<numbers.length;j++){
               if (numbers[i] +numbers[j]==x){
               if (i!=j){
                   rows++;
               }}
    }} 

    int [][]b = new int [rows][2];
    for (int i = 0; i<numbers.length;i++){
           for (int j = 1;j>=i && j<numbers.length;j++){
                   if(numbers[i]+numbers[j] == x){
                                    if (i!=j){
                        b[a][0] = i;
                        b[a][1] = j;
                        a++;
                    }}
    }
    }return b; 
    }
}

Copy/paste the whole thing, and you are good to go.

[JamesCherrill]

The inner loop code is wrong. With i == 1 it will exit on the very first execution because ! j>i

Why not just use the simple form for the inner loop ...

for (int j = i+1; j < numbers.length; j++) {

[Slavi]

Copy/Paste the whole thing didn't work as good as expected :D by the way, I am sorry for spamming on the thread lookin for answers but I spent pretty much all day and couldn't get it to compile correct at all, new ideas are always good I guess so DaniwebRules >.>

But then I changed it to @James's idea, and it worked, got 2 stars for it( out of 3). I kinda feel like I cheated on this one but owell couldn't move to the next section without it:( Thanks guys =)