CODEWITHSUNDEEP
javaarrays
Ajinkya
Ajinkya

Reputation: 855

Square Value at Index without using a temp array

At 0th index value is 4, so I have to check the value at index 4 and square it and place the value at 0th index without using a temp array:

Index  0 1 2 3 4
Values 4 3 1 2 0
================
Result 0 4 9 1 16

Now I am getting the first two values right, but the last three are not right. My code is as below:

static void Index(int arr[], int n) {
    for(int i=0;i<n;i++) {
        int index = arr[i];
        int value = arr[index];
        arr[i]=value*value;
        
    }
}

Below is the output that I am getting:

Original Array
4 3 1 2 0 
Array after Squaring 
0 4 16 256 0

Can anyone help me out here as to what am I doing wrong?

Upvotes: 1

Views: 483

Answers (3)

Chetan Seth
Chetan Seth

Reputation: 11

NOTE: This approach is valid only if length of array is less than 10. I have completed this code using only one loop without using any extra space. Although, I have set a flag to run the complete loop twice. If you do not have any constraint of using one loop, you can avoid using the flag and simply use two loops.

Approach:

Index           0  1  2  3  4
Values          4  3  1  2  0 
Updated value  04 23 31 12 40

You must have got the idea what I did here. I put the values at tens place whose square is to be displayed. Now you have to just have to iterate once more and put the square of tens place at that index Here's the code:

void sq(int arr[], int n){
    bool flag = false;
    for(int i=0; i<n; i++){
        if(!flag){
            if(arr[arr[i]] < 10){
                arr[i] += (arr[arr[i]] * 10);
            }
            else{
                arr[i] += ((arr[arr[i]]%10) * 10);
            }
        }
        if(i==n-1 && !flag){
            i=0;
            flag = true;
        }
        if(flag)
            arr[i] = (arr[i]/10) * (arr[i]/10);
    }
}

It is in C++.

Upvotes: 1

Bubletan
Bubletan

Reputation: 3863

Assuming the numbers are within range [0, 46341), we can store both the old and the new values in the array during the process (as 32 bits are enough). Then after the first loop we do another one to discard the old values and square the new ones.

// assume array[i] is within range [0, 46341) for any i
static void f(int[] array) {
    for (int i = 0; i < array.length; i++) {
        int j = array[i] & 0xffff; // get old value
        array[i] = array[j] << 16 | j; // put new and old values
    }
    for (int i = 0; i < array.length; i++) {
        int j = array[i] >>> 16; // get new value
        array[i] = j * j; // put new value squared
    }
}

Upvotes: 1

luckydog32
luckydog32

Reputation: 909

The problem is you are changing the values in your original array. In you current implementation this is how your array changes on each iteration:

{4, 3, 1, 2, 0} 
{0, 3, 1, 2, 0} 
{0, 4, 1, 2, 0} 
{0, 4, 16, 2, 0} 
{0, 4, 16, 256, 0}

The problem is you still need the values stored in the original array for each iteration. So the solution is to leave the original array untouched and put your values into a new array.

    public static void index(int arr[]) {
    int[] arr2 = new int[arr.length];
    for(int i=0;i<arr.length;i++) {
        int index = arr[i];
        int value = arr[index];
        arr2[i]=value*value;
    }
}

Values of arr2 in revised process:

{0, 0, 0, 0, 0} 
{0, 0, 0, 0, 0} 
{0, 4, 0, 0, 0} 
{0, 4, 9, 0, 0} 
{0, 4, 9, 1, 0} 
{0, 4, 9, 1, 16}

Upvotes: 0

Related Questions