CareerCup

Simple approach by use % and / operator with size of array.
e.g {2, 4, 3, 1, 0}
1. new value of A[0]= A[2] ,
so newValue= A[2]%size; (old value of A[2])
A[0]= A[0]+newValue*size; by doing this step, we have old value of A[0]=A[0]%size , new Value of A[0] = A[0]/size;
do this for every element
2. When first loop complete and every element has updated value(both old and new value) then run another loop and do A[i]=A[i]/size;
then every index of array has new value.

code based on above aproach

int size=A.length;
int newValue=0
for(int i=0;i<size;i++){
newValue=A[A[i]]%size;
A[i]=A[i]+newValue*size;
}
for(int i=0;i<size-1;i++)
A[i]/=size;

Time complexity is O(n) and auxillery space complexity is O(1)

// Program to assignments based on the index value of a given array
//  A[0...n-1] with elements [0,n-1] shuffle across array
// for example  Input : A[5] = { 2,4,3,1,0}
//   Output : A[5] = { 3,0,1,4,2}
// Solution 1 : Another array B[A[i]] = A[i]
// Solution 2 : In case of inplace 

int[] Modify(int input[], int n){

// Boundary conditions
if(input == null || n<=0) return null;

// Declaration
int pIndex=0 , qIndex=0,counter = 0;

// Initialization
do{
    pIndex= qIndex;
    qIndex= input[pIndex];
    //Swap(input,pIndex,qIndex);
    input[pIndex] =    input[pIndex] +    input[qIndex] ;
    input[qIndex] =    input[pIndex] -    input[qIndex] ;
    input[pIndex] =    input[pIndex] -    input[qIndex] ;

}while(++counter != n);

// Returning function
return input;
}

Nice try ..but the code is wrong .

At second time the loop gives p=q=2.
So it will keep on swapping the value p[2] with p[2] itself which is useless.

example:=

input array={2,4,1,3,0}

at first iteraqtion it will give = {1,4,2,3,0}

now what????????

p[2] with p[2]??

could you please write the task normally, it is impossible to understand it.

sure ...i will give an example suppose we have an array (2,1,3,5,4,0)(having n distinct integers starting from 0 to n-1). we have to modify it such that..

a[0] becomes a[a[0]] means a[0] having value 2 here so a[0] will become a[2] that is 3 here and rest all in the same way. so output should be following

3,1,5,0,4,2. got it?? here we have 0 to n-1 integers and 0 to n-1 positions as well.

sorry for imconvinience... my question is following:

suppose we have an array having 0 to n-1 distinct integers example {2,1,4,3,5,0} our goal is to modify this array such that a[0] becomes a[a[0]] means a[ 0] has value 2 here so a[0] = a[2] and so on . having the following output
{4,1,5,3,0,2}. 3 things are to be noted here that a) positions have range 0 to n-1 and values have range 0 to n-1 too (obviously). b)no extra array or link list or any data structure should be taken .c) should hav time complexity O(n).

Sorry for the inconvenience . My question is following :
Suppose we have an array of length n. The array has distinct values from 0,1,2....n-1 in any order(sorted or unsorted). for example lets take the array as {2,1,3,5,4,0}.

we have to modify it such that a[i]=a[a[i]] which means a[0] becomes a[a[0]] and so on..in the following example the output should be:-

a[0] = 2 so a[0]=a[2]=3
a[1] = 1 so a[1]=a[1] = 1
a[2] = 3 so a[2] = a[3] = 5
.
.
and so on.
we will get the following output:
{3,1,5,0,4,2}. got it?

3 things are to be noted here
a) values of elements lies in the set {0 to n-1} and positions are also 0 to n-1 obviously.
b) Time complexity = O(n)
c) No extra array or any DS should be used .

Solve it if you can .

the idea is the following:
at each iteration we dynamically increase the size of the array and write new values a[ a[ i ] ] to the end of that array.
After the cycle we just move the array head pointer to the middle of the array.
O(n).
But I suspect you will say, that it is not permitted to dynamically increase the size of the array, though there is no such prohibition in the initial task.

ok, here is the solution you wanted.
c# implementation.
All restrictions are observed. No additional data structures, no dynamical modifications of the initial array's size.
Time complexity O(n).

using System;

namespace ArrayTrick {

    class Program {

        static void Main(string[] args) {

            var arr = new[] { 2, 1, 3, 5, 4, 0 }; // output should be { 3, 1, 5, 0, 4, 2 }

            Process( arr );

            for ( int i = 0; i < arr.Length; i++ ) {
                Console.Write($"{arr[i]} ");
            }

            Console.ReadLine();
        }

        private static void Process( int[] arr, int i = 0 ) {
            int index = i;
            if (i < arr.Length ) {
                var val = arr[ arr[ i ] ];
                i++;
                Process( arr, i );
                arr[ index ] = val;
            }
        }
    }
}

hmmm my mistake . but here you are using a recursive function that means extra stack space in memory. moreover can u give the algo for what u wrote

nothing you are right . I think this is the perfect solution thanks a lot.

hey if u can solve without recursion

Here is the complete program O(n), (1)
#include<iostream>
using namespace std;
int main()
{
int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++)
{
index=a[a[i]]%n;
a[i]=a[i]+n*index;
//cout<<a[i]<<" ";
//index=i;
//call(a,i,n,b)
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";

}

return 0;
}

#include<iostream>
using namespace std;
int main()
{
	int a[]={2,1,3,5,4,0};
	//OutPut: {3,1,5,0,4,2}
	int n=6;
	int index=0;
	for(int i=0;i<n;i++)
	{
		index=a[a[i]]%n;
		a[i]=a[i]+n*index;
		//cout<<a[i]<<" ";
		//index=i;
		//call(a,i,n,b)
		}
		for(int i=0;i<n;i++)
		{
		 a[i]=a[i]/n;
		 cout<<a[i]<<" ";
		
		}
		
		return 0;
}

#include<iostream>
using namespace std;
int main()
{
	int a[]={2,1,3,5,4,0};
	//OutPut: {3,1,5,0,4,2}
	int n=6;
	int index=0;
	for(int i=0;i<n;i++)
	{
		index=a[a[i]]%n;
		a[i]=a[i]+n*index;
		//cout<<a[i]<<" ";
		//index=i;
		//call(a,i,n,b)
		}
		for(int i=0;i<n;i++)
		{
		 a[i]=a[i]/n;
		 cout<<a[i]<<" ";
		
		}
		
		return 0;

}

int a[]={2,1,3,5,4,0};
//OutPut: {3,1,5,0,4,2}
int n=6;
int index=0;
for(int i=0;i<n;i++)
{
index=a[a[i]]%n;
a[i]=a[i]+n*index;
//cout<<a[i]<<" ";
//index=i;
//call(a,i,n,b)
}
for(int i=0;i<n;i++)
{
a[i]=a[i]/n;
cout<<a[i]<<" ";

}

int a[]={2,1,3,5,4,0};
	//OutPut: {3,1,5,0,4,2}
	int n=6;
	int index=0;
	for(int i=0;i<n;i++){
		index=a[a[i]]%n;
		a[i]=a[i]+n*index;
		}
		for(int i=0;i<n;i++)
		{
		 a[i]=a[i]/n;
		 cout<<a[i]<<" ";}

public static void main(String args[]) {
System.out.println("Ques2");

int A[] = {2, 1, 3, 5, 4, 0};

System.out.println(Arrays.toString(A));

recursive(0, A, 0);

System.out.println(Arrays.toString(A));
}

static void recursive(int len, int A[], int currIndex) {

if(len == A.length) {
return;
}

int save = A[A[currIndex]];
recursive(len+1, A, A[currIndex]);

A[currIndex] = save;

}

I think we are dealing with only time complexity here not space. Following would do it in O(n) time
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main()
{
//declare/define all the required local variables first
int a[] = {2,1,3,5,4,0}, i = 0, n = 0, *out = NULL, err = 0;

//find out he size of orginal
n = sizeof(a)/sizeof(int);

//allocate the memory for temp array
out = (int *)calloc(n, sizeof(int));
if(out == NULL)
{
err = -1;
printf("ERROR: Internal error.\n");
goto exit;
}

//clone the array in temp array
for(i=0; i<n; i++)
{
out[i] = a[i];
}
//solution
for(i=0; i<n; i++)
{
if(a[i] > n)
{
err = -1;
printf("ERROR: Array contains invalid value\n");
goto exit;
}
a[i] = out[a[i]];
}

//display the output
printf("\nOUTPUT:");
for(i=0; i<n; i++)
{
printf(" %d", a[i]);
}

exit:
if(out)
{
free(out);
out = NULL;
}
return err;
}