Skip to main content

Josephus Problem using Queue

//Josephus.java
//Out of  n members, every m'th person will be eliminated
import java.io.*;

//Stack---------------
class Node<T> {
    T value;
    Node<T> link;
}

class Stack<T> {
    Node<T> top;
    public Stack() {
        top = null;
    }
    public void push(T item) {
        Node<T> n = new Node<T>();
        n.value = item;
        n.link = top;
        top = n;
    }
    public T pop() {
        T item;
        item = top.value;
        Node<T> n = top;
        n = null;
        top = top.link;
        return item;
    }
    public void display() {
        Node<T> n = top;
        System.out.print("(top)");
        while (n != null) {
            System.out.print(" ->" + n.value);
            n = n.link;
        }
        System.out.println();
    }
}

// Queue---------------------------
class Queue<T> {
    Node<T> front, rear;
    Stack<T> s1 = new Stack<T>();
    Stack<T> s2 = new Stack<T>();
    public Queue() {
    }
    public void add(T item) {
        while (s2.top != null)
            s1.push(s2.pop());
        s1.push(item);
        rear = s1.top;
        while (s1.top != null)
            s2.push(s1.pop());
        front = s2.top;
    }
    public T remove() {
        T item = s2.pop();
        front = s2.top;
        return item;
    }
    public void display() {
        Node<T> n = s2.top;
        System.out.print("(front)");
        while (n != null) {
            System.out.print(" <-" + n.value);
            n = n.link;
        }
        System.out.println(" <-(rear)");
    }
}

// Josephus Problem-------------------
public class Josephus {
    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new Queue<Integer>();
        Queue<Integer> q1 = new Queue<Integer>();
        int n, m, i;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter no. of members (n) : ");
        n = Integer.parseInt(br.readLine());
        System.out.println("Enter the elimination number (m) : ");
        m = Integer.parseInt(br.readLine());
        for (i = 1; i <= n; i++)
            q.add(i);
        Node<Integer> node = q.front;
        int l, k = 0;
        while (k != n - 1) {
            for (i = 1; i < m; i++)
                q.add(q.remove());
            l = q.remove();
            q1.add(l);
            k++;
        }
        System.out.println("Order of elimination is : ");
        while (q1.front != null)
            System.out.print(q1.remove() + ",");
        System.out.println("nWinner is : " + q.remove());
    }
}

Comments

Popular posts from this blog

Karabiner: Mouse/keyboard customizer for OS X

For beginners, or the one who migrated from Windows environment, Natural Gestures (Scrolling and Swiping) might be bit confusing. But, once you get familiarized with them, it may feel like "What was I doing, all those days?". It all changed, when I connected external mouse to my Macbook. When you start using that WHEEL, you will be confused. Luckily there is a setting for mouse, to change scroll behavior (natural or the other way). But, here's the catch. If you toggle that setting, it also toggles the same for TRACKPAD!!!!! I've seen that many people were freaked out and even raised BUG report to Apple. But, all those reports were closed, saying that is not a bug, but intentional feature!!! For those, who can't leave with such one-sided settings, here is a simple util, which came to my rescue: Karabiner It's simple, powerful and stable mouse/keyboard customizer for OSX. Without going into much detail, here's the configuration I used to ret...

USB port not working on Mac

Recently I connected  an external hard-disk   to my new MacBook and observed that it was not properly detected on one of the USB ports. But I can see that it is powering my HDD. I tried switching to other port and it worked. I simply ignored it by thinking that my HDD cable might be loose. Now I bought a new USB drive and to get it detected, I have to insert and detach it multiple times. And as usual, I suspected the new USB drive, as my Mac is brand new. And planned to replace my USB drive. Now my HDD came back to   my mind. And also my earlier laptop, in which few KEYS went unresponsive due to accumulated charges. By little researching I found that I'm not alone. The solution that worked for me was "Resetting SMC" Here is the procedure I followed: Shut down the Mac and connect the power cable Hold down Shift+Control+Option+Power concurrently for a few seconds. When the light on the power adapter blinks or changes colors you’ll know SMC r...

Divide : Separate work and play on one device

Recently I came across this beautiful app, while searching for good email app for corporate account. This app not only helps you in managing your emails, but also divides your work life from normal life, which can be accessed like switching between launchers. From Play Store: Divide delivers the ultimate mobile productivity tool to get work done securely on your Android device. Check your work email, view your calendar, look up contacts and more, all in one encrypted workspace without worrying about your privacy or the threat of your company wiping your device. Divide syncs with Exchange ActiveSync, Google Apps, and Lotus Notes and offers a complete BYOD solution for individuals and IT. Link: Divide