Advertisement
end1dream

Shortest Subsequence Given Operations

Nov 27th, 2015
183
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 1.14 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. /// <summary>
  5. /// I can't figure out how to backtrack and print the solution
  6. /// </summary>
  7.  
  8. namespace _678.Problem_10
  9. {
  10.     class Program
  11.     {
  12.         static void Main(string[] args)
  13.         {
  14.             int n = 5;
  15.             int m = 16;
  16.             int sum = n;          
  17.  
  18.             Queue<int> subsetFinder = new Queue<int>();
  19.             subsetFinder.Enqueue(n);
  20.             while (sum < m)
  21.             {
  22.                 sum = subsetFinder.Dequeue();
  23.                 // Console.Write(sum + " ");
  24.  
  25.                 if ((sum * 2) <= m && !subsetFinder.Contains(sum * 2))
  26.                 {
  27.                     subsetFinder.Enqueue(sum * 2);  
  28.                 }                                      
  29.                 if ((sum + 2) <= m && !subsetFinder.Contains(sum + 2))
  30.                 {
  31.                     subsetFinder.Enqueue(sum + 2);
  32.                 }                    
  33.                 if ((sum + 1) <= m && !subsetFinder.Contains(sum + 1))
  34.                 {
  35.                     subsetFinder.Enqueue(sum + 1);
  36.                 }
  37.             }      
  38.         }
  39.     }
  40. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement