Advertisement
sylviapsh

Find a sequence of given sum S

Jan 10th, 2013
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.58 KB | None | 0 0
  1. using System;
  2. using System.Collections.Generic;
  3. class FindSequenceOfSumSInArray
  4. {
  5.   static void Main()
  6.   {
  7.     //Write a program that finds in given array of integers a sequence of given sum S (if present).
  8.     //Example:   {4, 3, 1, 4, 2, 5, 8 }, S=11 -> {4, 2, 5}
  9.  
  10.     int[] myArray = { 5, 3, 3, 4, 2, 5, 8 };
  11.     int sumS = 11;
  12.  
  13.     List<int> sumSStartIndex = new List<int>();//A list array for the start index of each sequence that equals the desired sumS
  14.     List<int> sumSEndIndex = new List<int>();////A list array for the end index of each sequence that equals the desired sumS
  15.  
  16.     int currentSum = 0, //Used to store the sum of the elements while searching for our sumS in the cycle
  17.         currentCounter = 0;//Counts how many sumS we have found in the array
  18.        
  19.     for (int i = 0; i < myArray.Length; i++) //Cycle through the elements: this gives us the start element
  20.     {
  21.       for (int j = i; j < myArray.Length; j++) //Cycle through the elements: this gives us the end element
  22.       {
  23.         currentSum += myArray[j]; //Sum each element
  24.         if (currentSum == sumS) //Check if the sum is equal to the desired SumS
  25.         {
  26.           sumSStartIndex.Add(i); //We have a winner so the start and end inex wil be saved in the lists
  27.           sumSEndIndex.Add(j);
  28.           currentCounter++; //The counter for how many sumS are found is increased
  29.           break;//We have a winner so there is no need to proceed with that j sequence and we break the inner loop
  30.         }
  31.       }
  32.       currentSum = 0; //Get ready to proceed with the next sequence to sum
  33.      
  34.     }
  35.  
  36.     //Print the results on the console
  37.     if (currentCounter > 0)//If we have found the desired sum print that there is/are currentCounter sum/s SumS in the array
  38.     {
  39.       Console.WriteLine("There {0} {1} {2} {3} in the array:", currentCounter == 1 ? "is" : "are", currentCounter, currentCounter == 1 ? "sum" : "sums", sumS);
  40.       for (int k = 0; k < currentCounter; k++)//A cycle to print the actual elemnts from myArray that sum up to our SumS
  41.       {
  42.         Console.Write("{");
  43.         for (int result = sumSStartIndex[k]; result <= sumSEndIndex[k]; result++)
  44.         {
  45.           if (result != sumSEndIndex[k])
  46.           {
  47.             Console.Write("{0}, ", myArray[result]);
  48.           }
  49.           else
  50.           {
  51.             Console.Write("{0}", myArray[result]);
  52.           }
  53.         }
  54.         Console.WriteLine("}");
  55.       }
  56.     }
  57.     else
  58.     {
  59.       Console.WriteLine("There isn't a sequence that has a sum {0} in the array", sumS);//No SumS is possible in the array
  60.     }  
  61.   }
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement