title: Pseudocode/Java basic array summing algorithm
body: <p>I just had this question on an final exam for an introductory CS course. I thought it was pretty interesting but I couldn't fully figure it out. I tried coding it out on Eclipse for a while and wasn't getting anywhere. I have a Biochem exam soon so I really should be studying for that but this is bugging me... Thought I would ask for help.</p>
  
  <p>Question -- Write an algorithm for the following: 
  Given an input array, A, with 2 indices -- start and stop -- calculate the sum between the two. The array is sorted and all elements belong to the set {1, 2, 3}. This algorithm must run in O(log(n)). So given an array {1, 1, 2, 2, 3, 3, 3, 3} with indices 1 and 5 it would return 11.</p>
  
  <p>This is what I have so far:</p>
  
  <pre><code>public static int findSum(int[] a, int start, int stop) {
  
      int sum = 0;
  
      int temp[] = new int[4];
      int mid = (start+stop)/2;
  
      while (mid &gt; start || mid &lt; stop) {
  
          if (a[mid+1]-a[mid] != 0) {
              temp[mid+1] = mid+1;
              temp[mid] = mid;
              mid++;
          }
          else {
              findSum(a, start, mid);
              findSum(a, mid+1, stop);
          }
      }
      for (int i = 4; i &gt; 0; i--) {
          if (temp[i] == 0) {
              temp[i] = temp[i-1];
          }
      }
      for (int i = 1; i &lt; 4; i++) {
          sum += i*(temp[i]-temp[i-1]);
      }
      return sum;
  }
  </code></pre>
  
  <p>Don't know if my logic is correct at all but my idea was to look for indices in the array where the numbers shift and to do so in a recursive manner where I keep splitting the array into two parts. With these indices, I can determine the frequency in which the numbers appear and thus multiply the numbers by these frequencies and add those up to calculate the sum.</p>
  
  <p>Pretty sure my algorithm has numerous flaws in it...</p>