Circle of People

The problem was related to algorithm and I just love do practice and learn new algorithms

What it does

Given a circle of people find the last person to be removed if you go around the circle removing every second person

How I built it

Initially I created a program to simulates the problem and find solutions using brute force and I was able to find a solution by observing the results

Challenges I ran into

I am pretty sure there is a math formula to find the result directly but I think the benefits of the could by keeping the solution clear and easier to understand make it good enough :P

Accomplishments that I'm proud of

I am proud to solve a problem by thinking out of the box and having an open mind approach to find a solution

Solution

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Practices {
    public class VanHackathonApp {
        public static void Main(string[] args) {
            //for (int i = 2; i < 100; i++) {
            //    List<int> list = new List<int>();
            //    for (int index = 1; index <= i; index++) {
            //        list.Add(index);
            //    }
            //    Console.WriteLine(i + " =  " + GetLastPersonRemoved(list));
            //}
            for (int i = 2; i < 100; i++) {
                Console.WriteLine(i + " =  " + GetLastPersonRemoved(i));
            }
            Console.ReadKey();
        }

        public static int GetLastPersonRemoved(List<int> list) {
            int removeAt = 1;
            while(list.Count > 1) {
                list.RemoveAt(removeAt);
                if (list.Count == 1) {
                    break;
                }
                if (removeAt == list.Count) {
                    removeAt = 1;
                } else if (removeAt == list.Count - 1) {
                    removeAt = 0;
                } else {
                    removeAt++;
                }
            }
            return list[0];
        }

        /// <summary>
        /// Given a circle of people find the last person person to be removed if you go around the circle removing every second person
        /// The solution for this problem was founded by observing the result for sequentials values of N.
        /// The method public static int GetLastPersonRemoved(List<int> list) was used to the the list.
        /// And the results are always an odd number starting on 1 and been incremented by 2. However it return to zero every time the N is power of 2
        /// So the algorithm consist of the following steps:
        /// 1 - Find the highest power of 2 smaller than N
        /// 2 - Find the difference between N and the power found on step 1
        /// 3 - Increment by 2 from X times, where X is the number found on step 2
        /// </summary>
        /// <param name="n">Number of people in the list</param>
        /// <returns>Last person to be removed</returns>
        public static int GetLastPersonRemoved(int n) {
            /*
             * Find the highest power of 2 that is smaller than n
             */
            int power = 1;
            while (Math.Pow(2, power) <= n) {
                power++;
            }

            power--;

            /*
             * Find the difference from N to the found power of 2
             */
            int value = n - (Int32) Math.Pow(2, power);

            /*
             * Find the final result
             */
            int result = 1;
            for (int i = 0; i < value; i++) {
                result += 2;
            }

            return result;
        }
    }
}

Built With

• c#