Find the maximum subarray of an integer array

Question: given an unsorted array of integers, find the subarray that yields the largest sum. For instance, if the input is {5, 2, -1}, then the output is subarray {5, 2} because it gives the largest sum (7 vs. 5 vs. 2 or 6).

Solution: this problem can be solved by using a modified version of Kadane's Algorithm. The strategy is to calculate the sum of each subarray and keep track of the sum, the start index and the end index of the subarray that gives the largest sum. Moreover, we calculate the sum of a subarray by adding the sum of the previous subarray with an additional element. For example, to calculate the sum of {5, 2, -1}, we add the sum of {5, 2}, which is 7, to the value of the next element, which is -1.

Here is our C++ method to solve the problem:

void findMaxSumSequence (int inputArray[], int size)
{
  if (size == 0)
    throw "Array Size is 0";

  int maxSum = inputArray[0];
  int maxStartIndex = 0;
  int maxEndIndex = 0;
  
  int curSum = inputArray[0];
  int curStartIndex = 0;
  

  for (int i = 1; i < size; i++)
  {
    if (curSum < 0)
    {
      curSum = 0;
      curStartIndex = i;
    }
    
    curSum = curSum + inputArray[i];

    if (curSum > maxSum)
    {

      maxSum = curSum;
      maxStartIndex = curStartIndex;
      maxEndIndex = i;
    }
  } 

  cout << "Start index: " << maxStartIndex << " End index: " 
        << maxEndIndex << " Max sum: " << maxSum << endl;
}

Explanation: this method accepts an array and its size as arguments. It prints out the start index, end index and the sum of the subarray that yields the max sum. Here are the main steps:

1. First, check if the array size is 0. If it is so, we throw an exception because there is nothing we need to do when the array is null.
2. Then, initialize variables: maxSum is the largest sum found. maxStartIndex and maxEndIndex are respectively the start index and end index of the subarray that yields the max sum. curSum is the sum of the current subarray that we're examining. curStartIndex is the start index of the current subarray we're checking.
3. Next, we loop through the array and start calculating the sum of subarrays one after another:
   
   If the sum of the current subarray is less than 0, we reset curSum to 0. Why? If the last subarray's sum is negative, we will only decrease the next subarray's sum by adding the previous subarray's sum with an additional number. For example, if the previous subarray's sum is -2, and the next element is 3, it's better to reset the sum to 0 and add 3 into 0 than to add -2 to 3.
   
   curSum = curSum + inputArr[i] calculates the sum of the current subarray by adding the sum of the previous subarray with the next value in the array.
   
   After that, if the sum of the current subarray is greater than the max sum then we replace the max sum with the sum of the current subarray. We also change the maxStartIndex to the start index of the current subarray and the maxEndIndex to the current index i.
   
   When the loop ends, maxSum will contain the largest sum found. maxEndIndex and maxStartIndex contain respectively the end and start index of the subarray that gives the largest sum. Thus, we just have to print out those values.

If you have any comment or another solution to this problem, please post in the comment below. I would love to learn about it. Thanks for reading and until next post!

Finding an integer that repeats odd number of times in an array of positive integers

Question: in an array of positive integers, all but one integer repeats odd number of times. Can you find that integers in O(n) time complexity?

Answer: in order to solve this problem in O(n) time, we need to use bitwise manipulation. Since there is only one integer that repeats odd number of times, we can use the XOR operator to find out that number. When a number XOR with itself, it will become 0. Thus, if a number appears a even number of times, it yield a result of 0. For example, given the array {2, 3, 2, 3}, we have 2 and 3 repeat two times (even). Thus, if we XOR all of them together we should get 0 as the result. However, if there is an odd repeated number, the result will be the value of that number! Here is the algorithm in C++:

  public int getIntOddlyOccured(int[] inputArr)
  {
    int oddNum = inputArr[0];
   
    for(int i = 1; i < inputArr.length; i++)
      oddNum = oddNum ^ inputArr[i];
   
    return oddNum;
  }

Explanation: our method takes an integer array as argument. It assumes that there is one and only one odd occurring number (conditions given by the question), so it will return that number and does no validation to see whether the input in fact has only one odd repeated number. In the body, the method loops through the array and XOR all the elements together. The result will be the oddly repeated number.

Example: let's do an example with this array {1, 4, 3, 4, 1}. The method first initializes the result oddNum to 1 and then does the for loop:

1. First iteration: oddNum = 1(0001) ^ 4(0100) = 5(0101) and i = 1
2. Second iteration: oddNum = 5(0101) ^ 3(0011) = 6(0110) and i = 2
3. Third iteration: oddNum = 6(0110) ^ 4(0100) = 2(0010) and i = 3
4. Fourth iteration: oddNum = 2(0010) ^ 1(0001) = 3(0011) and i = 4
5. Loop ends because i = 5, so we return oddNum = 3 which is the oddly repeated number in the array

This algorithm takes O(n) time complexity because it loops through the array only once. The space complexity is O(1) because we only need an additional integer for storage. Very efficient! That's all we have for now. Thanks for reading :)

Check if two singly-linked lists intersect

Question: given two singly linked lists, determine if they intersect one another without modifying them.

Understand the question: first of all, we need to understand what intersecting linked lists are. Let's say we have two linked lists 1->2->3->4->5 and 10->20->30->5, they intersect each other because each list passes through the node 5. It's hard to visualize it in our head, so here is the picture:

Solution: to know whether two lists intersect, we just have to check if they share any common node. This is easy to be done with two pointers. One starts at the head of one list while the other starts at the head of the other list. Those pointers will run till the end of their lists or till they meet (pointing to the same node). If they meet, the two linked lists intersect. But if one pointer reaches the end of its list and hasn't met the other pointer yet, then the two linked lists do not intersect.

However, there is a small problem with our approach. When the lists have different lengths such as the ones in our example, the two pointers may never meet even if the lists intersect. Thus, we need to take into account that situation.

One way to solve that problem is to find out the lengths of the list. If they have different lengths, we'll calculate the difference in number of nodes between the shorter list and the longer list. Then, we'll move the pointer of the longer list ahead by that many nodes before starting to check for intersection. Our pointers are guaranteed to meet if there is intersection. Here is the implementation in Java:

private static boolean areListsIntersected(Node list1, Node list2)
{
    if (list1 == null || list2 == null)
      return false;

    if (list1 == list2)
      return true;

    int list1Len = 0;
    Node it1 = list1;
    while (it1 != null)
    {
      list1Len++;
      it1 = it1.next;
    }

    int list2Len = 0;
    Node it2 = list2;
    while (it2 != null)
    {
      list2Len++;
      it2 = it2.next;
    }

    int lenDiff = 0;
    it2 = list2;
    it1 = list1;

    if (list2Len > list1Len)
    {
      lenDiff = list2Len - list1Len;
      
      while (lenDiff > 0)
      {
        it2 = it2.next;
        lenDiff--;
      }
    }
    else if (list1Len > list2Len)
    {
      lenDiff = list1Len - list2Len;
      while (lenDiff > 0)
      {
        it1 = it1.next;
        lenDiff--;
      }
    }

    while (it2 != null && it1 != null)
    {
      if (it2 == it1)
        return true;
      it1 = it1.next;
      it2 = it2.next;
    }

    return false;
}

Explanation: our method takes two lists as arguments. It returns true if those lists intersect and false if they don't. The first two if statements are used to check for null lists and special case where the head of one list is the end node of the other list. When there are no null or special lists, we do the following:

1. First while loop counts the number of nodes in the first list.
2. Second while loop counts the number of nodes in the second list.
3. After having the length of each list, we find the difference in number of nodes and then move whichever pointer that points to the longer list ahead using that difference.
4. Finally, the while loop is used to find the intersection. We just loop until either of the pointers reaches the end of its list. During the loop, if the pointers meet, we return true immediately because it means that the lists intersect. But at the end of the loop and nothing has happened, we simply return false because the lists don't intersect.

You may notice that the pointers will meet at the first node that both lists share! Thus, this algorithm can be tweaked a little bit to return the intersection node of two intersecting lists. Or, this algorithm can be used to break two intersecting lists at their intersection node. Pretty neat huh?

Anyway, time complexity is O(m + n) where m and n are the number of nodes in the first and second list respectively. The space complexity is O(1).

Thanks for reading and until next time.

Convert integer to binary or bit string

Question: write a function to convert an integer into a bit string. For example, if input is 2, the output is "00000000000000000000000000000010" if the system is 32-bit, "0000000000000010" if the system is 16-bit and so on.

Solution: the strategy here is to use bitwise manipulation and convert one bit at a time to character. We look at the right most bit and if it is a 0 bit, we add '0' character into our bit string. Otherwise, we add '1' character into our bit string. Here is the code in C++:

char* int2bin(int num)
{
  const int BITS_PER_BYTE = 8;

  int bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char); 

  char* p = (char*)malloc(bitStrLen);

  for (int i = (bitStrLen - 1); i >= 0; i--)
  {
    int k = 1 & num;
    *(p + i) = ((k == 1) ? '1' : '0');
    num >>= 1;
  }
  
  return p;
}

Explanation: our function takes an int as the argument and returns a char pointer which points to the bit string. Also, remember that there are 8 bits per byte, that's why we have that constant declared in the first line.

1. Allocating memory from the heap to store our bit string: each bit is represented by a char ('0' or '1'). Thus, to get the total number of bytes required, we need the total of bits our integer has, and the number of bytes each char needs.
   
   To get the total number of bits each integer has, we use sizeof(int) * BITS_PER_BYTE. sizeof(int) gives the number of bytes each integer has, and BITS_PER_BYTE is the number of bits each byte has. Thus, multiplying them together, we have the total number of bits each integer has.
   
   To get the number of bytes each char needs, we just call sizeof(char)
   
   By multiplying the number of bits the integer has with the number of bytes each char needs, we get the total number of bytes required to store the binary string representation of the integer. Hence, bitStrLen = sizeof(int) * BITS_PER_BYTE * sizeof(char).
   
   
2. Next, we explicitly allocate enough memory from the heap to store our bit string by calling the malloc function.
   
   
3. Finally, we convert the integer into bit string using the for loop. Notice that the number of bytes we need is also the number of characters the bit string has. That's why our loop needs to run from 0 to 32 only.
   
   For each iteration, we check the right most bit of the integer by using bitwise manipulation: 1 & num. If the outcome is 1, then the right most bit must be 1. Otherwise, the right most bit must be 0. This works because any number with 1 at the right most bit will give the result of 1 when it AND with the number 1. But if the right most bit is 0, then the result is 0. For example, 1101 & 1 = 1 because 1101 has 1 as the right most bit.
   
   After converting the current right most bit, we need to shift the integer to the right one position to convert the next bit. Hence, num >>= 1
   

That's all we have for this post. If there is any suggestion or better solution, please leave it in the comment section below :) Thanks for reading!

Introduction to Thread in Java (part 2): Thread Life Cycle

Welcome to the second installment of the series "Introduction to Thread in Java." If you haven't read part 1, here is the link for you. Please read it because we covered a lot of important and fundamental concepts in the first part.

In this section, we'll learn more about the life cycle of threads. Specifically, we need to learn what states threads go through and why / how they end up in a particular state.

Overview

In the simplest form, a thread's life cycle consists of five states:

1. New state: this is when the threadable / Thread object is first created by calling the constructor of the Thread class. For example, our thread is in new state after this statement Thread newThread = new (runnableObj, threadName);
2. Runnable / Read-to-run state: after calling the start() method on the thread, it enters the runnable state. That means it is ready to run or to go to some other states. As of the current version of Java, a thread must enter the runnable state before going to any other state.
3. Running state: a thread is in this state while its run() method is executing. During this state, the thread can go to blocked state if it gets blocked or has to wait for other threads. When the run() method finishes, this state ends.
4. Blocked/waiting state: while running a thread can be put to sleep, interrupted or blocked by other threads. There are many reasons why this may happen. We'll go deeper in the next section.

5. Terminated / dead state: when a thread reaches this state, its life ends. It can never be revived again. Normally, a thread enters this state because its run() method has ended. However, a thread can also be terminated even before it is in the runnable state or during the waiting state by calling stop() or suspense() on the thread. I don't suggest using any of those methods to move a thread to its terminated state because those methods have been deprecated by Java and are not thread safe. Therefore, ending the run() method is the best way to go. We'll discuss more on how to do that later.

Here is the UML state diagram that describes the states that a Java thread goes through and how it gets to those states.

Next, let's examine the Blocked/Waiting state and the Terminated/Dead state. They are more complicated than other three states.

Blocked / Waiting state

As we have seen, a thread can only enter this state while it is running. So why does a thread enter this state? There are many causes. The main three are:

1. Yielding for another thread: current thread yields for another thread to run first. Sometimes, we have a particular thread that needs to run immediately, so we call the yield() method on any running thread to reclaim CPU and resources for the important thread. As the result, any running thread enters the blocked state until the important thread finishes and releases the CPU / resources.
2. Waiting for another thread: somewhat similar to yielding, there are times when a thread needs to wait for another thread to finish first before it can continue. For instance, if two threads share the same resource, and one of the two is holding that resource, then the other thread needs to wait for that resource to be released.
3. Waiting for I/O: as you may know, the I/O speed is extremely slow compared to the CPU speed. Thus, if a thread needs some resources / inputs from I/O, it may need to enter the waiting state in order to let the CPU work on other threads. This practice is better for utilizing the CPU because it should be working on other threads / processes instead of siting idle and waiting for a particular thread.

The Java Thread API provides all functions needed to resolve all the situations above. For example, the join() method allows one thread to wait for the completion of another thread. Moreover, you can always cause a thread to enter the waiting state at anytime by calling the method interrupt() on that thread (there are some cases where threads are not interruptable however). Here is the link to the Java Thread API for further reading.

Terminated / Dead State

Once a thread enters this state, it cannot come back to other states. There two distinct ways to terminate the thread, letting the run() method return and calling stop(), suspense() or destroy() method on the running thread. The former is recommended because it ensures thread safe. In fact, Java has already deprecated stop(), suspense() and destroy() method in the new API.

Here is an excellent article that points out why those methods are bad and why stopping a thread through run() is a good practice.

That's all for the second part of this series. Please leave any comment or suggestion because they are always helpful and appreciated :)

Removing a loop in a singly linked list

Challenge: remove a loop from a singly linked list if the list has a loop. For example, 1->2->3->4->1 (4 points to the head node 1) should become 1->2->3->4 while 1->2->3->4 should stay the same 1->2->3->4.

Solution: the first task is to determine if our linked list has a loop. If it does, we then need to figure our where the end of the loop is. The reason is that we will set the pointer of the loop's end node to NULL to break the loop. For instance, given the list 1->2->3->1, we must find out whether it has loop. Obviously, that list does have a loop and the loop's end node is 3 (3 points back to head of the loop which is 1). Thus, we need to make node 3 point to NULL so the list doesn't have a loop anymore. The result should be 1->2->3->NULL. Here is the C++ implementation of the algorithm:

#include<iostream>
using namespace std;

struct Node
{
  int data;
  Node* next;
};

void removeLoop(Node* head)
{
  if (head == NULL)
    return;

  Node* slow = head;
  Node* fast = head;
  Node* last = NULL;
  
  bool hasLoop = false;

  while (fast->next != NULL && fast->next->next != NULL) 
  {
    last = slow;
    slow = slow->next;
    fast = fast->next->next;
    
    if (slow == fast)
    {
      hasLoop = true;
      break;
    }
  }

  
  if (hasLoop)
  {
    slow = head;

    while (slow->next != fast->next)
    {
      slow = slow->next;
      fast = fast->next;
    }
    
    if (slow == head && fast == head )
      last->next = NULL;
    else
      fast->next = NULL;
  }
}

Explanation: our method takes only the reference to the list's head node as an argument. The first while loop determines if the list has loop. And, the second while loop points the loop's end node to null, terminating the loop:

1. If the list is empty (head points to NULL), there is nothing to do so return.
2. Next, we need three different pointers. slow will go through the list one node after another. fast moves through the list two nodes at a time, so it goes twice as fast as the slow pointer. And, last refers to the previous node visited by the slow pointer.
3. We just have to loop through the list until fast reaches NULL because if the linked list doesn't have loop, fast will reach NULL eventually. Moreover, if the list does have a loop, we'll break out of the while loop immediately.
4. As the while loop runs, we check if slow and fast pointer point to the same node. When they do, it means the list has a loop. This is a very common technique to find out if a linked list has loop. Here is a post about that technique if you are not familiar with it.
5. As soon as we know that the list has loop, we set the flag hasLoop to true. And then, we break out of the while loop immediately because fast will never reach NULL and the while loop will never end.
6. If the list has loop as indicated by the flag hasLoop, we enter the second while loop to remove that the list's loop.
   
   a) First, we set the slow pointer back to the list's head node.
   
   b) Then, we move both the slow and fast pointer one node at a time. They will eventually meet each other because the list still has a loop.
   
   c) We stop the loop right before the pointers meet. That's how we get the reference to the end node of the loop:
   
   d) If the slow and fast pointer both point to the head of the list, then the list is circular, meaning that the end node points back to the head node of the list (ie. 1->2->3->4->1). Thus, we'll get the reference to the end node by using the last pointer. Remember that last is pointing to either the head of the list or the end node of the loop after the first while loop. That's why if slow and fast point at the head, then slow must be pointing at the end node.
   
   e) On the other hand,if the end node is pointing to any node in the list other than the head node (ie. 1->2->3->4->2), then slow and fast is pointing to the end node and last is pointing to the head node. Thus, we use fast pointer instead of last pointer to break the loop.
   
   

This algorithm takes O(n) time complexity and O(1) space complexity. It's very efficient!!

Find all subsets of a given set

If we're given a set of integers such that S = {1, 2, 3}, how can we find all the subsets of that set? For example, given S, the subsets are {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, and {1, 2, 3}.

To solve this problem there are two techniques that we need to understand:

1. Determine the number of subsets using bit strings: we know that the number of subsets equals to 2 to the power of the number of elements in the superset: #subsets = 2 ^ #elements. For instance, if our superset is S = {1, 2, 3}, then it has 2^3 = 8 subsets. If our superset has four elements then it has 2^4 = 16 subsets. Moreover, by shifting the bit representation of the number 1 by n, we also get 2^n. Thus, if we shift the bit string of 1 by the number of elements in the superset, we'll get the number of subsets for that superset. For example, if we have S = {1, 2, 3}, then there are 1 << 3 = 2^3 subsets in S.
2. Keeping track of data using bit manipulation: for this problem, we will use a bit string to keep track of subsets and their elements. Take S = {1, 2, 3} as an example. If the bit string is 100 then the subset we're working on has only one element which is 1. If the bit string is 110 then the subset we're working on has two elements which are 1 and 2. We will use & and << bit operators to figure out which bit is 1 in the bit string.

If you are not familiar with bit manipulation please read "Bit manipulation tips & tricks" part 1 and part 2. Here is the code for the algorithm written in Java:

private static void findSubsets(int array[])
{
  int numOfSubsets = 1 << array.length; 

  for(int i = 0; i < numOfSubsets; i++)
 {
    int pos = array.length - 1;
   int bitmask = i;

   System.out.print("{");
   while(bitmask > 0)
   {
    if((bitmask & 1) == 1)
     System.out.print(array[pos]+",");
    bitmask >>= 1;
    pos--;
   }
   System.out.print("}");
 }
}

Code explanation:

1. First, we find out the number of subsets that the superset has by shifting the bit representation of 1 by the number of elements in the superset.
2. Next, we just loop through each subset and generate its elements accordingly.
3. Inside the loop, we use pos and bitmask to keep track of the element. Specifically, bitmask is the bit string that represents elements in the current subset. And, we use post to retrieve the correct element from the superset.
4. The while loop will add the correct element to the subset. Note that bitmask & 1 equals to 1 only when bitmask has a '1' bit at the last position. For example, bitmask = "001" or "011" will make bitmask & 1 equal to 1. That's when we'll add an element into the subset. Why does it work? Well, for each iteration of the while loop, we'll shift bitmask by one bit position to the right (bitmask >>= 1) and we decrement pos by 1 (pos--). Thus, whenever there is a '1' bit at the last bit position, we know exactly which element to add into the subset. If you are confused, don't worry because we'll do an example!
5. After finishing one subset, we go to a new line and continue processing the rest.

Example: supposed that we have S = {1, 2} as our superset, then numOfSubsets = 0001 << 2 = 0100 = 4 (subsets). The rest of the program runs like this:

1. i = 0, pos = 1, and bitmask = 0. First while loop iteration, bitmask & 1 = 0, bitmask >>= 1 = 0, and pos = 0. While loop exits because bitmask = 0.
2. i = 1, pos = 1, and bitmask = 1. First while loop iteration, bitmask & 1 = 1, so print out array[pos] = 2. bitmask >>= 1 = 0 and pos = 0. While loop exits because bitmask = 0.
3. i = 2, pos = 1, and bitmask = 2. First while loop, bitmask & 1 = 0, so print nothing. bitmask >>= 1 = 1 and pos = 0. Second while loop, bitmask & 1 = 1, so print out array[pos] = 1. bitmask >>= 1 = 0 and pos = -1. While loop exits because bitmask = 0.
4. i = 3, pos = 1, and bitmask = 3. First while loop, bitmask & 1 = 1, so print out array[pos] = 2. bitmask >>= 1 = 1 and pos = 0. Second while loop, bitmask & 1 = 1, so print array[pos] = 1. bitmask >>= 1 = 0, and pos = -1. While loop exits because bitmask = 0.

The result is 4 subsets: {}, {2}, {1} and {2, 1}

This algorithm can be challenging to understand if you don't have any knowledge about bit manipulation. So, if you have a hard time making sense of it, try to read about bit manipulation first! That will help a lot! Well, thanks for reading and until next time.

Algorithm to determine if a linked list is circular or has a loop

Problem: how do you find out if a linked list is circular (ie. 1->2->3->4->1) or has a loop (ie. 1->2->3->4->2)?

Understand the problem: a circular linked is like a circle where the end node points to the head node instead of null like in a regular linked list. The example, 1->2->3->4->1, has the end node 4 points to the head node 1, creating a cycle. Similarly, a linked list is said to have a loop when it contains a cycle. However, the cycle doesn't have to start at the head node. It can start at any node in the list. For instance, 1->2->3->4->2 has a loop that starts at node 2 and ends at node 4.

Solution: to solve this problem, we'll have two pointers moving at different speeds over the list. The slow pointer will move through the list one one at a time while the fast pointer will move over two nodes at a time. In other words, the fast pointer will move twice as fast as the slow pointer. When the slow and fast pointer point at the same node, we know that the linked list either is circular or has a loop. But if the linked list is just a regular list, the fast pointer will reach null before the slow pointer.

Algorithm implementation: here is the algorithm implemented in C++

#include<iostream>
using namespace std;

struct Node
{
  int data;
  Node* next;
};

bool hasLoopInList(Node* head)
{
  if (head == NULL)
    return false;

  Node* slow = head;
  Node* fast = head;

  while (fast->next != NULL && fast->next->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;

    if (slow == fast)
      return true;
  }

  return false;
}

Code explanation:

1. Check whether the list is empty. If it is, return false because an empty list neither is circular nor has loop.
2. Create two pointers, slow and fast, that are used to traverse the list and determine if the list has loop or not. Initially, these pointers will point at the first node in the list.
3. Next, we just need to loop until our fast pointer reaches null or until the slow and fast pointer points at the same node. If the list is just a regular list, nothing will happen inside the while loop. And, the while loop will end eventually because the fast pointer will reach null. On the other hand, if the list has loop or is circular, the slow and fast pointers will eventually point at the same node. That's why we check for that condition for every iteration of the while loop. And as soon as we know the list has a loop, we return true.

This is a very efficient way to find out if a linked list has loop or is circular. The time complexity is O(n) where n is the number of nodes in the list. Moreover, the space complexity is O(1) because we only need two pointers no matter how long the list we need to check is.

Converting ASCII representation of positive numbers to integer

A number can be represented as ASCII characters (char) or integers (int). Thus, the question is how we can convert from char to int. For example, we want to convert '123' to 123 or '45' to 45.

To solve this problem, we need to revisit the ASCII table for a little bit. Moreover, we are interested in the characters '0' to '9' in the table. The special thing about those characters is that they stand consecutively in the table. That means their decimal values are consecutive positive integers. For example, '0' is 48; '1' is 49; and '2' is 50. Thus, if we have '1' - '0', we'll get an integer value of 1 because 49 - 48 = 1. That's how we're gonna convert the number from char to int. Here is the algorithm in C++:

#include<iostream>
#include<math.h>
using namespace std;

int digitsToInt(char arrayOfChars[], int size)
{
  int digitPos = size - 1;
  int result = 0;
  for (int i = 0; i < size; i++)
  {
    result += ((int)(arrayOfChars[i] - '0')) * pow(10, digitPos);
    digitPos--;
  }
  return result;
}

Explanation: our function takes an array of characters containing the char representation of the number and the size of the array.

1. digitPos keeps track of which digit we're converting. It is important to do so because we must convert the digit into appropriate value in integer (remember that ASCII digits are between '0' and '9'). If the number passed in is '102', then the first digit '1' represents 100 in integer. The algorithm must know that and multiply '1' with 100 after converting it into int 1.
2. result is the final number in int. Our strategy here is to convert each digit into its appropriate int value and then add all of them up. That will give us the final result in integer. For example, if we need to convert '12', we will convert '1' to 1 first and multiply it by 10. Next, we convert '2' to 2 and multiply it by 1 (2 is the last digit). Therefore, the final result is 10 + 2 = 12.
3. We loops through the array and convert each digit into the appropriate int value and add that value into the result. As explained above, by subtracting the digit by '0' and casting the result into int we'll get the correct int number corresponding to that digit. However, that's not all. Notice how we use the function pow(10, digitPos) to get the correct value for each digit. This method works because our numbers are base 10 numbers. Thus, by multiplying a number by 10 to the power of its position, we'll get the correct value for that number. Don't worry if you are confused, we'll do an example later.
4. Lastly, we decrement digitPos by one because we will move to process the next digit which has one order less than the current number.
5. Return the final result which is the sum of all the int values of our digits.

Example: we'll convert the number '123' into integer.

1. Our digitPos is 2 because we process the first digit '1' first and it is in the hundredth position. So, '1' - '0' gives int 1. Then, 1 * 10 ^ 2 = 100. Add that into our result. We have 100 after the first iteration. Moreover, digitPos decreases by 1 because we are about to process the tenth digit.
2. Second iteration, digitPos is 1. And we have '2' - '0' = int 2. Multiplying 2 by ten to the power of its position, we have 2 * 10 ^ 1 = 20. Add that value to the result and we end up with the sum of 120. Finally, we decrement digitPos by 1.
3. Last iteration, digitPos is 0. And, '3' - '0' = int 3. Multiplying 3 by ten to the power of its position, we have 3 * 10 ^ 0 = 3. Add 3 into the result and we have int 123. Loop ends and our algorithm returns the result of 123.

Thanks for reading and as always feel free to leave any comment or suggestion :)