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

OS X 10.8 Mountain Lion bootable USB (without MAC)

Download the raw file from here . How to use: 1 - Copy the .raw file to an USB stick using  SUSE Studio Image Writer . If you have error during copy, eject and re-connect the pen drive. When Windows asks if you want to format it, cancel and run Image Writer again. If the problem persists, disable your anti-virus software, it may be blocking raw write to the drive. Another Image Writer for Windows, if SUSE doesn't work https://launchpad.net/win32-image-writer/+download 2 - Boot the USB drive and install. If you need, type  boot options , for example: -v (verbose boot) [default] -x (safe) -s (single user) GraphicsEnabler=yes (enable graphics card drivers) [default] USBBusFix=yes (fix problems with USB devices) npci=0x2000 (use if boot stops at "PCI configuration begin") cpus=1 If you need, use  TransMac  to remove kexts which are causing problems (System/Library/Extensions) and use the flag -f (ignore caches) at boot, or remove /System/Libra...

JavaScript - Singleton Pattern

The singleton design pattern is probably the simplest and most common pattern in JavaScript. So why should you use the singleton pattern? Encapsulation of members & functions Creates its own Namespace A singleton is a single instance object Encourages code reuse Improves readability because you can logically organise your code The point of a singleton is to only have one instance. A shopping cart is a good example of something that you may want only a single instance of at one time. The simplest form of Singleton is an object literal. This loose form of Singleton cannot be instantiated. All of the members are now accessible through the Singleton variable, accessible through dot notation. var myCart = {     self: this ,     totalCost: 0,     totalQty: 0,     cart: {},     getCart: function (){ },     updateCart: function (){ } }; alert( "Total cost: ...

Java: Use BigInteger in for-loop

In my previous post , I mentioned a way to handle large integers by using BigInteger. Now I'm going to provide a very important usage of it. We often use for-loop. So here is the way to use it: Ordinary integers: for(int i = 1; i <= n; i++) {  //Task to do } BigInteger: for (BigInteger bi = BigInteger.valueOf(1);                 bi.compareTo(n) <= 0;                 bi = bi.add(BigInteger.ONE)) { //Task to do } here n is a BigInteger variable.