Why Using the 'Return' Keyword is Crucial in Programming: Lessons from My Experience with the Josephus Problem.

Hello to every one,

Last month, I had an interesting incident that I would like to share today.

As a curious individual, I came across the Josephus problem when my friend Abinash posed it as a recursion question. Intrigued, I decided to explore the problem further and conduct some research on its history. What I found was fascinating! The Josephus problem has a rich and intriguing past, and its impact on the field of mathematics is significant. With this newfound knowledge, I felt better equipped to tackle the problem and create a solution. So, what exactly is the Josephus problem, and how did I solve it? Keep reading to find out!

The Josephus problem is a famous mathematical puzzle named after the ancient historian Josephus, who, as the story goes, devised a brilliant strategy to survive a battle.

According to the tale, Josephus and a group of Jewish soldiers were trapped in a cave by Roman soldiers during the First Jewish-Roman War. Instead of surrendering or fighting to the death, Josephus suggested a plan for the soldiers to commit suicide in a specific order that would leave only one person alive at the end. The last surviving soldier would then surrender to the Romans, who would spare his life.

The soldiers formed a circle, and starting from the first person, every other soldier was to be killed until only one person remained. However, Josephus did not want to be the first to die, so he devised a clever strategy. He and his friend agreed to start from the third person, and then Josephus would continue counting every third person until only one person was left. In this way, Josephus ensured that he would be the last one standing.

I was thrilled to solve the Josephus problem after learning about its fascinating history. I quickly started coding my first draft but ran into issues when it failed to run and threw an index out-of-bound error. I tried debugging and running it again, but the problem persisted, and I encountered other errors as well. Despite taking short breaks, I spent three hours on it and finally came up with a draft that still didn't work. At that point, I realized that I had to quit trying to solve it.

Feeling defeated, I called my friend Abinash to inform him that I couldn't solve the problem. He admitted that he had also tried but was unable to find the solution. We had a brief conversation, and I thanked him for presenting such an intriguing problem. I also asked him to give me more challenging questions like this in the future.

The code was this-

private static int Josephus(int n, int k, boolean[] arr,int killed,int i,int counter,int ans) {
    if (killed != n - 1) {

        if (counter == k&& !arr[i]) {
            arr[i] = true;
            if (i < n-1)
                Josephus (n, k, arr, killed + 1, i + 1, 1,ans);
            else
                Josephus (n, k, arr, killed + 1, 0, 1,ans);
        }
        if (counter == k&& arr[i]){
            if (i < n-1)
                Josephus (n, k, arr, killed, i + 1, counter,ans);
            else
                Josephus (n, k, arr, killed, 0, counter,ans);
        }
        if (!arr[i]) {
            if (counter < k && i != n-1)
                Josephus (n, k, arr, killed, i + 1, counter + 1,ans);
            else
                Josephus (n, k, arr, killed, 0, counter + 1,ans);
        } else {
            if (counter < k && i != n-1)
                Josephus (n, k, arr, killed, i + 1, counter,ans);
            else
                Josephus (n, k, arr, killed, 0, counter,ans);
        }
    }
    else
        ans= survivor(arr);
    return ans;
}


private static int survivor(boolean[] arr){
    int i;
    for (i = 0; i < arr.length; i++) {
        if(!arr[i])
            break;
    }
    return i+1;
}

Every time I ran my code for the Josephus problem, it kept giving me an error. I spent hours trying to debug it and finally discovered that it was reaching the answer, but instead of returning the output, it kept running unnecessary functions.

After ending my call with Abinash, I sat staring at my IDE screen and realized that all the 'Josephus' functions were executing, even though it was not necessary. In a state of exhaustion, I began to wonder if adding a return keyword before all the 'Josephus' functions would fix the problem. It may sound silly, but I was willing to try anything at that point. To my surprise, it worked!

Return prevented it from running unnecessary functions!

And the new code was this-

private static int Josephus(int n, int k, boolean[] arr,int killed,int i,int counter,int ans) {
    if (killed != n - 1) {

        if (counter == k&& !arr[i]) {
            arr[i] = true;
            if (i < n-1)
                return Josephus(n, k, arr, killed + 1, i + 1, 1,ans);
            else
                return Josephus(n, k, arr, killed + 1, 0, 1,ans);
        }
        if (counter == k&& arr[i]){
            if (i < n-1)
                return Josephus(n, k, arr, killed, i + 1, counter,ans);
            else
                return Josephus(n, k, arr, killed, 0, counter,ans);
        }
        if (!arr[i]) {
            if (counter < k && i != n-1)
                return Josephus(n, k, arr, killed, i + 1, counter + 1,ans);
            else
                return Josephus(n, k, arr, killed, 0, counter + 1,ans);
        } else {
            if (counter < k && i != n-1)
                return Josephus(n, k, arr, killed, i + 1, counter,ans);
            else
                return Josephus(n, k, arr, killed, 0, counter,ans);
        }
    }
    else
        ans= survivor(arr);
    return ans;
}


private static int survivor(boolean[] arr){
    int i;
    for (i = 0; i < arr.length; i++) {
        if(!arr[i])
            break;
    }
    return i+1;
}

I reached out to my friend again to let him know that my code was finally working. He asked me if I had updated my solution on the GFG terminal, which I realized was an important step. After submitting my updated code, I felt a sense of nervous excitement as I awaited the output.

I ended up submitting multiple attempts just to take a screenshot, but finally, I saw the desired output. My friend congratulated me on my accomplishment and commended me for my hard work and effort.

I then asked him to give me his piece of code which he by seeing the solution wrote and he gave me this-

class Solution
{
    public static int josephus(int n, int k)
    {
        ArrayList<Integer> al = new ArrayList<>();
        for (int i = 1; i<=n; i++) {
            al.add(i);
        }
        solve(k-1, al, 0);
        return al.get(0);
    }
    static void solve(int k, ArrayList<Integer> al, int index) {
        if(al.size()==1) return;
        index = (index+k)%al.size();
        al.remove(index);
        solve(k, al,index);
    }
}

After seeing his code I grabbed my head that my code was so large, but I was happy that at least I solved it :)