Using only if-else statements to find specific element in an array with length n and elements from 0-CodePudding

I'm stuck in solving an interview question. The goal is to find a specific element from an array with unknown length (cannot use .length) and return the number of steps, but for an array with a length of n, the elements are guaranteed to be from 0 to n-1, no duplicates. For example, if the array's length is 5, the elements are {0, 1, 2, 3, 4} but the order may be different. Additional requirements are no loops, no static/global variables, and no helper functions, and the only parameters passing in are the array int[] arr and the target value int x, no extra parameters allowed, the array remains the same after all the operations have done.

//So you can only write in the body of the following method, no outside variables nor methods could be used.

private int findElement (int[] arr, int x) {

}

What I have gotten so far is, since the elements are guaranteed to be 0 to n-1, I can use the target number as an index and go back to the array to see if the number arr[x] equals the number x I want. If not, I take that number arr[x] and make it my new index, repeating until I find the target value.

int[] arr = {4, 1, 0, 2, 3}
int target = 3;
arr[3] = 2; //take target as the initial index
arr[2] = 0;
arr[0] = 4;
arr[4] = 3; //we got the number we want
//steps total is 3 since the question says the first time doesn't count.

Question: I tried to solve this by recursion, but since I am always comparing the following values with the initial parameter value, in the above case I always wanted to find 3. So how to store that information without static variables or extra parameters is my bigges problem. Is there any other way I can store the initial parameter value and pass it through the whole process?

    private int findElement(int [] arr, int x) {
        int actualN = arr[x];
        if (actualN == **???**) { //can't be x cuz x is changing but I always want 3
            return 0;
        } else {
            return findElement(arr, arr[x])   1;
        }

    }

Preferably using Java Any hints or help would be greatly appreciated.

CodePudding user response：

You were almost there

    // t is the target number, o is teh array offset
    static int find(int [] arr, int t, int o) {
        if (arr[o] == t)
            return o;
       return  find(arr, t, o   1);
    }

and

    static void Main(string[] args) {
        int[] arr = { 4, 1, 0, 2, 3 };
        int target = 3;
        int x = find(arr, 3, 0);
   }

CodePudding user response：

Probably this should work:

private int findElement(int [] arr, int x) {
        int currValue = arr[x], returnValue;
        if(arr[x]>0)   
            arr[x] = 0;//setting the actual element of the array to 0
        else
            arr[x]--;// decrementing the search index so it goes from 0-> -1 -> -2 -> -3...
        if(Math.abs(arr[-arr[x]]) == x)//We check if the number is at our search index...
            returnValue = 0;
        else        
            returnValue = findElement(arr, x) 1;
        arr[x] = currValue;//We take the value of the index from when the function was called and then reassign it to the same index after our work with it is done.

        return returnValue;
}

Since the array only has to be the same after execution and it doesn't matter it's state during execution, this may work. Note: I haven't done elaborate test on this so please do test the code sometimes before submitting