# Array and Strings

### Array Problems

#### Sum of 2 numbers

We are given a sorted array A of length n and a value k. We want to find out if there are indices i, j such that A[i] + A[j] == k.

Give a Θ(n) way of solving this problem. Prove its running time and correctness.
Your algorithm should also output one pair of indices i, j such that A[i] + A[j] == k (if at least one pair exists; if multiple exist, you only need to output one of them).

Other variant of the same problem
When array is not sorted
We need to find pair of numbers in an array whose sum is equal to a given value.
Input [6,4,5,7,9,1,2]
Sum = 10
Then the pairs are [6,4] , [9,1]

Solution

There are three solutions

Sorted array
1. When array is sorted, take two index variable. Indx1 point to fisrt index and Indx2 points to the last index
2. If Indx1 + Indx2 < sum then increment the Indx1
3. Else if Indx1 + Indx2 > sum then decrement Indx 2
4. If Indx 1 > Indx 2 then halt -> No pairs found

If pair found then keep doing the same to find next pair.

Hashing/Binary Map
Another solution works for both sorted and unsorted array. In this approach we not actually using the hash function fundamental idea is to maintain the occurrence of number i.e. Binary Map

The caveat is that we need extra memory.

1. Get the number from input array
2. Num2 = Sum - arr[i]
3. If we have encountered Num2 already in input array then we found a pair i.e.
if(binMap[Num2] == 1)
4. Else record input element in Binary map i.e. binMap[arr[i]] = 1;

Bit Vector

This approach is similar to Binary map except using array for extra space we use bit vector to save some of extra space.

This program works for max for 31 as bit map is int which is 32 bits. For numbers more than 31 more memory could be allocated.

#### Sum of 2 numbers greater or equal to given sum*

We are given a sorted array A of length n and a value k. We want to find out if there are indices i, j such that A[i] + A[j] >= k.

Your algorithm should also output all the pairs of indices i, j such that A[i] + A[j] >= k

#### Sum of 3 numbers*

We need to find three numbers in an array whose sum is equal to a given value.

#### Find repeating/duplicate numbers*

Find all the numbers repeating in a array

Input [2,1, 3, 2, 3, 1, 4]

Output [2,1,3]

#### Find the number when size of array is unknown*

Given an array of integers find the given element is present when size of array is not given

Input array 2,1, 3, 2, 3, 1, 4

Element to find 3. Find solution in less than O(n) time.

#### Merge two sorted array

Input array1 [1, 3, 6, 7]
Input array2 [1, 2, 4]

Output [1, 1, 2, 3, 4, 6, 7]

#### Merge 2 non sorted array and remove duplicates

Input array1 [6, 3, 6, 1, 7]
Input array2 [5, 1, 2, 4, 6]

Output could be in sorted order or non-sorted order based on algorithm you choose to solve it.

Output [1, 2, 3, 4, 5, 6, 7] OR
Output [6, 3, 1, 7, 5, 2, 4] OR
Output [5, 1, 2, 4, 6, 3, 7] OR
Output [6, 5, 3, 1, 2, 4, 7] etc…

#### Sort array based on count

Given number in array [2, 1, 3, 2, 1, 4] sort array based on count of numbers.

Sort them as [1, 1, 2, 2, 3, 4]

#### Find odd number of occurrence

Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.

#### Find 2 numbers with odd occurence

Given an unsorted array that contains even number of occurrences for all numbers except two numbers. Find the two numbers which have odd occurrences in O(n) time complexity and O(1) extra space.

Input: [12, 23, 34, 12, 12, 23, 12, 45]
Output: 34 and 45

Input: [4, 4, 100, 5000, 4, 4, 4, 4, 100, 100]
Output: 100 and 5000

Input: [10, 20]
Output: 10 and 20

Solution Explanation

#### Searching an Element in a Rotated Sorted Array

This article explains the reasoning for searching an element in a rotated sorted array.

It even explains how to find the minimum number i.e. from where rotation started.

#### Largest Sum Contiguous Subarray

Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Array [-2, -3, 4, -1, -2, 1, 5, -3]
Sum 7

#### Permute numbers

Write all the non repeating permutations of given numbers i.e.

Input = [1, 2, 3, 4]
Output
1 2 3 4
1 2 3 4
1 2 4 3 …

This problem is on the same footstep of string permutation

### String Problems

#### Reverse a string without extra space

String could be reversed without using extra space using bitwise operator XOR

#### Duplicates and Count

Print all duplicate characters and their count

Input string
Foo Bar

Output
a1B1F1o2r1

#### Remove all consecutive duplicate elements

Remove all consecutive duplicate elements from the string

Input string
aabbccddd

Output
abcd

#### Rotate a string

Rotate a string for a ‘n’ times

Input string
1234567
len = 7
Rotate 2 times

Output
3456712

Step 1

Break array into 2 parts from index 2 as number of time to rotate is 2

[1 2] [3 4 5 6 7]

Step 2

Reverse both arrays

[2 1] [7 6 5 4 3]

Step 3

Reverse all

Result = [3 4 5 6 7 1 2]

Permutation