Number summation problem

Very recently, I have come across an interesting programming problem which is shown below.

Problem :: We have an array of various numbers. From that array we need to find those numbers which can be written as sum of 2 or more consecutive numbers existing within the same array.

Say for example, in an array of numbers (5,1,3,2,4,6), the first number "5" can be written as "3+2" but not "1+4" as "1" and "4" are not appearing consecutively. Similarly "6" can be written as "5+1" and "2+4" etc. 

So, we need to find out all the numbers which are sum of other consecutive numbers and print them.

1. So, will be requiring a loop which would inspect every number in the array (starting from 5,1 and so on). Let's examine the case of "5".

2. Inside the above loop, we start with adding-numbers (which would be added to produce "5") "1" and start checking if consecutive numbers "3", "2" (i.e 1+3+2+...) and so on can produce the sum "5".
   So, we need a second loop for this. This would find the starting point of adding-numbers. A successful series may be "1+3+..." or "3+2+.." or "2+4+.." etc. So, 1,3,2 etc are starting numbers from which we start to add consecutive numbers.

3. Now, let's consider a case where we have such a starting number say "1". We need a third loop which would run through rest of the array to add consecutive numbers "3", "2" etc  to "1" and produce a sum of "5". This third loop will produce the actual sum.

4. We keep a track whether minimum 2 numbers are added to produce the final result "5" through a counter.

Let's check the code part to understand our approach to solve the problem. The inspection of number "5" have been discussed in comments in the code below.

<?php
// Define the array
$arr = array(5,1,3,2,4,6);

// Here we have the FIRST loop to inspect 
// each number in the array
for($i=0;$i<count($arr);$i++)
{
  // Store the Current number we are inspecting
  // Let's examine the case of 5
  $current_number = $arr[$i];
  
  // Second Loop
  for($j=0;$j<count($arr);$j++)
  {
      // Set $sum variable to hold SUM
      $sum = 0;
      $str = "";
 
      // $count variable makes sure that minimum
      // two numbers are added
      $count = 0;
 
      // We would ignore the Number we are inspecting
      // while Addint. We won't add "5" to $sum 
      // (initially set to 0) to product "5". 
      // Hence we just ignore the situation
      if($j == $i) continue;  
 
      // Otherwise, We move ahead
      if($j != $i) 
      {
  
        // Third Loop, it keeps on Adding to $sum from 
        // the starting point say "1" or "3" or "2" and so on.
        for( $k=$j;$k<count($arr);$k++)
{

          // Avoid the chance of adding the Number
           // which is being inspected (5 in our test case)
          if($k == $i) break;
 
       // Add to SUM ($sum variable)
          $sum += $arr[$k];
  
   // When we add, we increase the counter
   // We need to make sure that minimum 2 numbers
   // are added to produce "5"
   $count++;
  
   // We build a String of numbers we are adding
   $str .= $arr[$k] . ",";
  
    // If summation is already higher than 
           // the Number being inspected, we discard 
           // that combination. This way we can 
           // discard "1+3+2" resulting 6 etc and 
    // save some precious CPU time
    if($sum>$current_number) 
           { 
              break; 
           }
  
          // If minimum 2 digits are added
           // and Sum is "5" let's PRINT the result 
           // and break. This means if we find that 
           // "3+2" is acceptable, then we need to 
           // move to next starting point say "2" and                          // check combinations like "2+4+..." etc
          if($count >= 2 && $sum == $current_number) 
          { 
            // Show Result
            echo "<br> ($i position)" .
                 " $current_number is summation" .
                 " of numbers ". rtrim($str,","); 
            break; 
          } 
      } // Third Loop Ends
    
     }// If ends
 
  } // Second Loop ends

} // First Loop Ends

?>

The above code is explained within the accompanied comments. 

Now, Check the output below :

(0 position) 5 is summation of numbers 3,2
(4 position) 4 is summation of numbers 1,3
(5 position) 6 is summation of numbers 5,1
(5 position) 6 is summation of numbers 1,3,2
(5 position) 6 is summation of numbers 2,4

Find longest substring inside a string

Very recently I have seen a small programming problem given on a site, which is shown below.

Find the length of the longest substring without repeating characters within a given string.

Take the string 'immediate' for example. The longest non-repeating letters would be "mediate". We can't accept "mmediate" because 'm' is repeating. 

In the string "borough", there are longest substring (non-repeating characters) will be "rough".

In the string "xxxxxx", the longest substring without non-repeating characters is "x".

So, we are going to write a program in PHP which would find the longest substring. And we are following this process ..

1. We would run a loop to examine the given string, reading character from 0th position, 1st position and so on.
2. We would pick up non-matching characters and store them in a character array. That array of characters will be converted to sub-strings.
3. Such sub-strings will be stored in a final array.
4. If we have a list of substrings, easily we can make out which is the longest substring among them using the strlen() function and a for loop.

Let's check out the final code :: 

<?php

// The given string is here
$str = "aksjdhiquywenqmneqkjosiqioueyqwemndfgppoiuytrewqasdfghyujikolrvcxzvbybnuimklopoiui";

// This is the final array where substrings will be stored
$subs = array();

// The main LOOP which reads the string
// So when $i is 0, the $str is read from 0th position
// When $i is 1, the $str is read from 1st position
for($i=0;$i<strlen($str);$i++)
{
  
  // A small array where picked-up characters will be stored
  $k = array();
  
  // Another loop which picks up characters from given string
  // and adds to the array $k  
  for($j=$i; $j<strlen($str); $j++)
  {
    // The array $k will be built with characters which are
    // not repeated earlier. So, we used in_array() to check
    // if this picked-up character is already existing in array $k
    if(!in_array( $str[$j], $k))
    {
       $k[] = $str[$j];
    }  
    else
    {
      // So we found a repeating character
      // So, BREAK to build the Substring
      break; 
    }
  }
  
  // When $k holds the series of characters
  // now build the substring and put it in the
  // array $subs
  $subs[] = implode("",$k);
}

// So, now $subs array holds all the possible substrings
// existing in the given string. Now is the time, we 
// find the longest among them
$max = 0; 
$final_str = "";

// Loop and scan
for($i=0; $i< count($subs); $i++)
{
  if(strlen($subs[$i]) > $max) 
  { 
      $max = strlen($subs[$i]); 
      $final_str = $subs[$i]; 
  }
}

// Finally print the result
echo "Max Length : $max, String : [$final_str]";
?>

The above code is quite self-explanatory. Each simply tries to create/extract substrings from the given string. For that we need to run a loop scanning from 0th position in the string $str. 

So, in the first pass, characters are picked up from 0th position in $str and kept in array $k till a non-matching character is found. Next the array $k is converted to a string (read substring) and put in the final array $subs.

In the 2nd pass, characters are picked up from 1st position in $str and kept in array $k and a substring is built eventually and kept in array $subs. 

This way, we build an array of all the possible substrings (made with non-repeating charaters) exist inside the string $str. 

And finally we simply decide which is the longest among them and print the result.

The above program displayed the output to be ::
Max Length : 21, String : [ewqasdfghyujikolrvcxz]