DEV Community: Darshan V ( Darshan Animus )

Josephus Problem | Iterative Solution | Java

Darshan V ( Darshan Animus ) — Fri, 25 Mar 2022 01:30:12 +0000

History
Josephus Problem is theoretical game named after flavius Josephus, he was historian, who was trapped along with his 40 soldiers in cave. Instead of surrendering to roman soldiers they choose to commit to suicide by drawing lots. Josephus states, by the grace of god or by luck, they were the only two to remain alive and surrender to roman soldiers.

Problem
There are 'n' number of people standing in a row waiting to be executed and only one remains alive. The problem has two values, one is the number of people and other is the way they are executed.

Example


Input : N = 5, K = 2
Output : 3
Firstly, the Person at position 2 is out, 
then position 0 goes out, then position 4
Finally, the Person at position 1 is out. 
So the Person at position 3 survives.

Input : 7 4
Output : 2

Solution

Time Complexity: theta(2^n)
Space Complexity: theta(1)

import java.util.Scanner;
import java.util.Arrays;

public class Jos {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int temp = n;
        int count = 0;
        boolean[] arr = new boolean[n];
        Arrays.fill(arr, true);
        for (int i = 0; i < temp; i++) {
            if (n != 1) {
                if (arr[i])
                    count++;
                if (count == k) {
                    arr[i] = false;
                    count = 0;
                    n -= 1;
                }
                if (i == temp - 1) {
                    i = -1;
                }

            } else {
                break;
            }
        }
        for (int j = 0; j < arr.length; j++) {
            if (arr[j])
                System.out.println(j);
        }
    }
}

100days code challenge

Darshan V ( Darshan Animus ) — Mon, 21 Mar 2022 01:19:31 +0000

*Recursion
*
Recursion is the process in which the function call itself until some condition(the condition is called the base case) is reached.

the key points in recursion are:-

Recursive Function call.
Base case.

Base case :- it is stopping condition of the recursive call.

syntax :- static int fact(int n) { if(n==0) return 1 return n*fact(n-1) }

Example:- Palindrome check using Recursion
Palindrome is a number, which viewed from both sides is same.

import java.util.Scanner;

//Palindrome check with recursion
public class Palli {
    public int temp = 0;

    static int getReverse(int n, int temp) {
        if (n == 0)
            return temp;
        temp = temp * 10 + n % 10;
        return getReverse(n / 10, temp);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, temp = 0;
        System.out.println("Enter the Number");
        n = sc.nextInt();
        int cnum = getReverse(n, temp);
        System.out.println(cnum);
        if (n == cnum)
            System.out.println("The Number is a pallindrome");
        else
            System.out.println("The Number is not pallindrome");
    }
}

Example 2:- Sum of Digits
The sum of digits is problem where a number is given and sum of each digit in the number must be calculated.
ex: 253 = 2+5+3 = 10

import java.util.Scanner;

public class SOD {
    static int soD(int n) {
        if (n == 0)
            return 0;
        return soD(n / 10) + n % 10;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(soD(n));
    }
}