Reverse a String

First Solution

void reverseString(char* str) { int len, loop;
char temp; len = strlen(str); for(loop = 0; loop < (len / 2); loop++) { temp = str[loop];
str[loop] = str[len - loop - 1];
str[len - loop - 1] = temp; } }

Second Solution

The second solution is slightly better than the first as it does not need the char space. It uses bit manipulation (XOR in this case) to swap the chars in place.

void reverseStringBetter(char* str) { int loop1 = 0, loop2; loop2 = strlen(str) - 1; for (loop1 = 0; loop1 < loop2; loop1++, loop2--) { str[loop1] ^= str[loop2] ; str[loop2] ^= str[loop1] ; str[loop1] ^= str[loop2] ; } }

Number of Ones

Write a function that determines the number of bits set to 1 in the binary representation of an integer.
Going by the brute force approach, it would be easy to come up with the following solution. If the least significant bit of a number is 1, it will return a result of 1 when we AND it with 1. Using this logic, we can shift bits in the number to the right and keep testing if the least significant bit is 1. When there are no 1’s left in the number, it will become zero. 

int numOnesInInteger(int num) { int numOnes = 0; while(num != 0) { if((num & 1) == 1) { numOnes++; } num = num >> 1; } return numOnes; }

Time Complexity: O(n) ==> Where n in the number of bits in the integer.

Improved Solution:

Let’s think, what happens to a number when it we AND it with (number – 1). Let’s take 7 (0111) as an example.

7 & 6 = 0111 & 0110 = 0110 = 6
6 & 5 = 0110 & 0101 = 0100 = 4
4 & 3 = 0100 & 0011 = 0000 = 0

Do you see a pattern yet? Essentially, when you AND a number with (number – 1), the last 1 bit in the number gets set to zero. So if we continue to set every 1 bit in the number to zero, the number will eventually become zero. If we use this logic to count the number of 1s, we have an algorithm that runs in O(m) where m is the number of bits set to 1 in the number. Here’s some code.

int numOnesInInteger(int num) { int numOnes = 0; while(num != 0){ num = num & (num – 1); numOnes++; } return numOnes; }

int main()
{
     int num, count = 0;
     printf(“Enter the number: “);
     scanf(“%d”,&num);
     count = number_of_ones(num);
     printf(“\nNumber of one’s are %d\n”, count);

     return 0;

}

Meaning of “referencing” and “dereferencing”

Referencing means taking the address of an existing variable (using &) to set a pointer variable. In order to be valid, a pointer has to be set to the address of a variable of the same type as the pointer, without the asterisk:

int  c1;
int* p1;
c1 = 5;
p1 = &c1;
//p1 references c1

Dereferencing a pointer means using the *operator (asterisk character) to access the value stored at a pointer. NOTE: The value stored at the address of the pointer must be a value of the same type as the type of variable the pointer "points" to. e.g. *p = *p +1; Note: & is the reference operator and can be read as “address of”.* is the dereference operator and can be read as “value pointed by”.

Search an element in a sorted and rotated array

#include <stdio.h>

int searchElementInRotatedArray(int arr[], int start, int end, int key) {
    while(start < end) {
        int mid = (start + end) / 2;
        if(arr[mid] == key) {
            return 1;
        }
        if(arr[start] <= arr[mid]) {
            if((key >= arr[start]) && (key <= arr[mid])) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        } else {
            if((key >= arr[mid]) && (key <= arr[end])) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
    }
    return 0;
}

int main() {
    int len, num;
    printf("Enter Length of Array: ");
    scanf("%d", &len);
    int arr[len];
    printf("Enter Elements of Array: ");
    for(int loop = 0; loop < len; loop++) {
        scanf("%d ", &arr[loop]);
    }
    printf("Enter Element to Search: ");
    scanf("%d", &num);
    (searchElementInRotatedArray(arr, 0, len, num))?printf("Key Found\n"):printf("Key Not Found\n");
    return 0;
}

Solution Using Temporary Array

Input arr[] = [10, 12, 23, 40, 53, 36, 78], d = 2, n =7
1) Store d elements in a temp array
   temp[] = [10, 12]
2) Shift rest of the arr[]
   arr[] = [23, 40, 53, 36, 78, 36, 78]
3) Store back the d elements
   arr[] = [23, 40, 53, 36, 78, 10, 12]

Time complexity O(n)
Auxiliary Space: O(d)

Implementation:

#include <stdio.h>

int main() {
    long num, rot;
    scanf("%ld %ld", &num, &rot);
    unsigned long arr[num];
    unsigned temp[rot];
    for(long loop = 0; loop < num; loop++) {
        scanf("%lu", &arr[loop]);
    }
    for(long loop = 0; loop < rot; loop++) {
        temp[loop] = arr[loop];
    }
    for(long loop = rot; loop < num; loop++) {
        arr[loop - rot] = arr[loop];
    }
    long index = 0;
    for(long loop = (num - rot); loop < num; loop++) {
        arr[loop] = temp[index++];
    }
    for(long loop = 0; loop < num; loop++) {
        printf("%lu ", arr[loop]);
    }
    return 0;
}

Compare two linked lists

int CompareLists(Node *headA, Node *headB)
{
    while((headA != NULL) && (headB != NULL)) {
        if(headA->data != headB->data) {
            break;
        }
        headA = headA->next;
        headB = headB->next;
    }
    if((headA == NULL) && (headB == NULL)) {
        return 1;
    } else {
        return 0;
    }
}

Reverse a Linked-List

void ReversePrint(Node *head)
{
    Node *prev = NULL, *curr = head, *next;
    if(head != NULL) {
        while(curr != NULL) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        head = prev;
        while(prev != NULL) {
            printf("%d\n", prev->data);
            prev = prev->next;
        }  
    }
}