Arrays

ARRAYS:
1.Program for array rotation

Given an array of integers arr[] of size N and an integer, the task is to rotate the array elements to the left by d positions.
Examples:  
Input: 
arr[] = {1, 2, 3, 4, 5, 6, 7}, d = 2
Output: 3 4 5 6 7 1 2
Input: arr[] = {3, 4, 5, 6, 7, 1, 2}, d=2
Output: 5 6 7 1 2 3 4

/*package whatever //do not write package name here */

import java.io.*;

class rotation_normal {


// Fuction to rotate array
static void Rotate(int arr[], int d, int n)
{
	// Storing rotated version of array
	int temp[] = new int[n];

	// Keepig track of the current index
	// of temp[]
	int k = 0;

	// Storing the n - d elements of
	// array arr[] to the front of temp[]
	for (int i = d; i < n; i++) {
		temp[k] = arr[i];
		k++;
	}

	// Storing the first d elements of array arr[]
	// into temp
	for (int i = 0; i < d; i++) {
		temp[k] = arr[i];
		k++;
	}

	// Copying the elements of temp[] in arr[]
	// to get the final rotated array
	for (int i = 0; i < n; i++) {
		arr[i] = temp[i];
	}
}

// Function to print elements of array
static void PrintTheArray(int arr[], int n)
{
	for (int i = 0; i < n; i++) {
		System.out.print(arr[i]+" ");
	}
}
	public static void main (String[] args) {
		int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
		int N = arr.length;
		int d = 2;

		// Function calling
		Rotate(arr, d, N);
		PrintTheArray(arr, N);
	}
}

Python:

# Python program to rotate an array by d elements

# Function to left rotate arr[] of size n by d
def Rotate(arr, d, n):
p = 1
while(p <= d):
	last = arr[0]
	for i in range (n - 1):
	arr[i] = arr[i + 1]
	arr[n - 1] = last
	p = p + 1
	
# Function to print an array
def printArray(arr, size):
for i in range (size):
	print(arr[i] ,end = " ")
	
# Driver code
arr = [1, 2, 3, 4, 5, 6, 7]
N = len(arr)
d = 2

# Function calling
Rotate(arr, d, N)
printArray(arr, N)


2.Reversal algorithm for Array rotation



Given an array arr[] of size N, the task is to rotate the array by d position to the left.
Examples: 
Input:  arr[] = {1, 2, 3, 4, 5, 6, 7}, d = 2
Output: 3, 4, 5, 6, 7, 1, 2
Explanation: If the array is rotated by 1 position to the left, 
it becomes {2, 3, 4, 5, 6, 7, 1}.
When it is rotated further by 1 position,
it becomes: {3, 4, 5, 6, 7, 1, 2}
Input: arr[] = {1, 6, 7, 8}, d = 3
Output: 8, 1, 6, 7

// Java program for reversal algorithm of array rotation


import java.io.*;

class LeftRotate {
	/* Function to left rotate arr[] of size n by d */
	static void leftRotate(int arr[], int d)
	{

		if (d == 0)
			return;

		int n = arr.length;
		// in case the rotating factor is
		// greater than array length
		d = d % n;
		reverseArray(arr, 0, d - 1);
		reverseArray(arr, d, n - 1);
		reverseArray(arr, 0, n - 1);
	}

	/*Function to reverse arr[] from index start to end*/
	static void reverseArray(int arr[], int start, int end)
	{
		int temp;
		while (start < end) {
			temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;
			start++;
			end--;
		}
	}

	/*UTILITY FUNCTIONS*/
	/* function to print an array */
	static void printArray(int arr[])
	{
		for (int i = 0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
	}
	public static void main(String[] args)
	{
		int arr[] = { 1, 2, 3, 4, 5, 6, 7 };
		int n = arr.length;
		int d = 2;

		leftRotate(arr, d); // Rotate array by d
		printArray(arr);
	}
}


PYTHON

# Python program for reversal algorithm of array rotation

# Function to reverse arr[] from index start to end


def reverseArray(arr, start, end):
	while (start < end):
		temp = arr[start]
		arr[start] = arr[end]
		arr[end] = temp
		start += 1
		end = end-1

# Function to left rotate arr[] of size n by d


def leftRotate(arr, d):

	if d == 0:
		return
	n = len(arr)
	# in case the rotating factor is
	# greater than array length
	//d = d % n
	reverseArray(arr, 0, d-1)
	reverseArray(arr, d, n-1)
	reverseArray(arr, 0, n-1)

# Function to print an array


def printArray(arr):
	for i in range(0, len(arr)):
		print (arr[i],end=' ')


# Driver function to test above functions
arr = [1, 2, 3, 4, 5, 6, 7]
n = len(arr)
d = 2

leftRotate(arr, d) # Rotate array by 2
printArray(arr)

Program-3

Program to cyclically rotate an array by one

Given an array, cyclically rotate the array clockwise by one. 
Examples:  

Input:  arr[] = {9, 10, 11, 12, 13}
Output: arr[] = {13, 9, 10, 11, 12}
Cyclically rotate an array by one



Solve Problem
Following are steps. 
1) Store last element in a variable say x. 
2) Shift all elements one position ahead. 
3) Replace first element of array with x.


import java.util.Arrays;

public class cyclical_rotate
{
	static int arr[] = new int[]{1, 2, 3, 4, 5};
	
	
	static void rotate()
	{
	int i = 0, j = arr.length - 1;
	while(i != j)
	{
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
		i++;
	}
	}
	
	/* Driver program */
	public static void main(String[] args)
	{
		System.out.println("Given Array is");
		System.out.println(Arrays.toString(arr));
		
		rotate();
		
		System.out.println("Rotated Array is");
		System.out.println(Arrays.toString(arr));
	}
}



Python

def rotate(arr, n):
	i = 0
	j = n - 1
	while i != j:
	arr[i], arr[j] = arr[j], arr[i]
	i = i + 1
	pass


# Driver function
arr= [1, 2, 3, 4, 5]
n = len(arr)
print ("Given array is")
for i in range(0, n):
	print (arr[i], end = ' ')

rotate(arr, n)

print ("\nRotated array is")
for i in range(0, n):
	print (arr[i], end = ' ')

Another Method

import java.util.Arrays;
 
public class Test
{
    static int arr[] = new int[]{1, 2, 3, 4, 5};
     
    // Method for rotation
    static void rotate()
    {
       int x = arr[arr.length-1], i;
       for (i = arr.length-1; i > 0; i--)
          arr[i] = arr[i-1];
       arr[0] = x;
    }
     
    /* Driver program */
    public static void main(String[] args)
    {
        System.out.println("Given Array is");
        System.out.println(Arrays.toString(arr));
         
        rotate();
         
        System.out.println("Rotated Array is");
        System.out.println(Arrays.toString(arr));
    }
}



Another Method in Python

# Python3 code for program to
# cyclically rotate an array by one

# Method for rotation
def rotate(arr, n):
	x = arr[n - 1]
	
	for i in range(n - 1, 0, -1):
		arr[i] = arr[i - 1];
		
	arr[0] = x;


# Driver function
arr= [1, 2, 3, 4, 5]
n = len(arr)
print ("Given array is")
for i in range(0, n):
	print (arr[i], end = ' ')

rotate(arr, n)

print ("\nRotated array is")
for i in range(0, n):
print (arr[i], end = ' ')


Search an element in a sorted and rotated Array

Given a sorted and rotated array arr[] of size N and a key, the task is to find the key in the array.
Note: Find the element in O(logN) time and assume that all the elements are distinct.
Example:  
Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 3
Output : Found at index 8
Input  : arr[] = {5, 6, 7, 8, 9, 10, 1, 2, 3}, key = 30
Output : Not found
Input : arr[] = {30, 40, 50, 10, 20}, key = 10   
Output : Found at index 3


Consider arr[] = {3, 4, 5, 1, 2}, key = 1
Pivot finding:
low = 0, high = 4:
        =>  mid = 2
        =>  arr[mid] = 5, arr[mid + 1] = 1
        => arr[mid] > arr[mid +1],
        => Therefore the pivot = mid = 2
Array is divided into two parts {3, 4, 5}, {1, 2}
Now  according to the conditions and the key, we need to find in the part {1, 2} 
Key Finding:
We will apply Binary search on {1, 2}. 
low = 3 , high = 4.
            =>  mid = 3
            =>  arr[mid] = 1 , key = 1, hence arr[mid] = key matches.
            =>  The required index = mid = 3
So the element is  found at index 3.


/* Java program to search an element
   in a sorted and pivoted array*/
 
class search_key {
 
    /* Searches an element key in a
       pivoted sorted array arrp[]
       of size n */
    static int pivotedBinarySearch(int arr[], int n,
                                   int key)
    {
        int pivot = findPivot(arr, 0, n - 1);
 
        // If we didn't find a pivot, then
        // array is not rotated at all
        if (pivot == -1)
            return binarySearch(arr, 0, n - 1, key);
 
        // If we found a pivot, then first
        // compare with pivot and then
        // search in two subarrays around pivot
        if (arr[pivot] == key)
            return pivot;
        if (arr[0] <= key)
            return binarySearch(arr, 0, pivot - 1, key);
        return binarySearch(arr, pivot + 1, n - 1, key);
    }
 
    /* Function to get pivot. For array
       3, 4, 5, 6, 1, 2 it returns
       3 (index of 6) */
    static int findPivot(int arr[], int low, int high)
    {
        // base cases
        if (high < low)
            return -1;
        if (high == low)
            return low;
 
        /* low + (high - low)/2; */
        int mid = (low + high) / 2;
        if (mid < high && arr[mid] > arr[mid + 1])
            return mid;
        if (mid > low && arr[mid] < arr[mid - 1])
            return (mid - 1);
        if (arr[low] >= arr[mid])
            return findPivot(arr, low, mid - 1);
        return findPivot(arr, mid + 1, high);
    }
 
    /* Standard Binary Search function */
    static int binarySearch(int arr[], int low, int high,
                            int key)
    {
        if (high < low)
            return -1;
 
        /* low + (high - low)/2; */
        int mid = (low + high) / 2;
        if (key == arr[mid])
            return mid;
        if (key > arr[mid])
            return binarySearch(arr, (mid + 1), high, key);
        return binarySearch(arr, low, (mid - 1), key);
    }
 
    // main function
    public static void main(String args[])
    {
        // Let us search 3 in below array
        int arr1[] = { 5, 6, 7, 8, 9, 10, 1, 2, 3 };
        int n = arr1.length;
        int key = 3;
        System.out.println(
            "Index of the element is : "
            + pivotedBinarySearch(arr1, n, key));
    }
}



Python Program:


# Searches an element key in a pivoted
# sorted array arrp[] of size n
def pivotedBinarySearch(arr, n, key):
 
    pivot = findPivot(arr, 0, n-1)
 
    # If we didn't find a pivot,
    # then array is not rotated at all
    if pivot == -1:
        return binarySearch(arr, 0, n-1, key)
 
    # If we found a pivot, then first
    # compare with pivot and then
    # search in two subarrays around pivot
    if arr[pivot] == key:
        return pivot
    if arr[0] <= key:
        return binarySearch(arr, 0, pivot-1, key)
    return binarySearch(arr, pivot + 1, n-1, key)
 
 
# Function to get pivot. For array
# 3, 4, 5, 6, 1, 2 it returns 3
# (index of 6)
def findPivot(arr, low, high):
 
    # base cases
    if high < low:
        return -1
    if high == low:
        return low
 
    # low + (high - low)/2;
    mid = int((low + high)/2)
 
    if mid < high and arr[mid] > arr[mid + 1]:
        return mid
    if mid > low and arr[mid] < arr[mid - 1]:
        return (mid-1)
    if arr[low] >= arr[mid]:
        return findPivot(arr, low, mid-1)
    return findPivot(arr, mid + 1, high)
 
# Standard Binary Search function
def binarySearch(arr, low, high, key):
 
    if high < low:
        return -1
 
    # low + (high - low)/2;
    mid = int((low + high)/2)
 
    if key == arr[mid]:
        return mid
    if key > arr[mid]:
        return binarySearch(arr, (mid + 1), high,
                            key)
    return binarySearch(arr, low, (mid - 1), key)
 
 
# Driver program to check above functions
# Let us search 3 in below array
if __name__ == '__main__':
    arr1 = [5, 6, 7, 8, 9, 10, 1, 2, 3]
    n = len(arr1)
    key = 3
    print("Index of the element is : ", \pivotedBinarySearch(arr1, n, key))
    
    
    
    Program:5
Arrangement Rearrangement :

Given an array of elements of length N, ranging from 0 to N – 1. All elements may not be present in the array. If the element is not present then there will be -1 present in the array. Rearrange the array such that A[i] = i and if i is not present, display -1 at that place.

Input : arr = {-1, -1, 6, 1, 9, 3, 2, -1, 4, -1}
Output : [-1, 1, 2, 3, 4, -1, 6, -1, -1, 9]

Input : arr = {19, 7, 0, 3, 18, 15, 12, 6, 1, 8,
              11, 10, 9, 5, 13, 16, 2, 14, 17, 4}
Output : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 
         11, 12, 13, 14, 15, 16, 17, 18, 19]


// Java program for above approach
class arrangement{
     
// Function to transform the array
public static void fixArray(int ar[], int n)
{
    int i, j, temp;
     
    // Iterate over the array
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
             
            // Check is any ar[j]
            // exists such that
            // ar[j] is equal to i
            if (ar[j] == i)
            {
                temp = ar[j];
                ar[j] = ar[i];
                ar[i] = temp;
                break;
            }
        }
    }
  
    // Iterate over array
    for(i = 0; i < n; i++)
    {
         
        // If not present
        if (ar[i] != i)
        {
            ar[i] = -1;
        }
    }
  
    // Print the output
    System.out.println("Array after Rearranging");
    for(i = 0; i < n; i++)
    {
        System.out.print(ar[i] + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int n, ar[] = { -1, -1, 6, 1, 9,
                     3, 2, -1, 4, -1 };
    n = ar.length;
  
    // Function Call
    fixArray(ar, n);
}
}
 

Python:

# Python3 program for above approach

# Function to transform the array
def fixArray(ar, n):
	
	# Iterate over the array
	for i in range(n):
		for j in range(n):

			# Check is any ar[j]
			# exists such that
			# ar[j] is equal to i
			if (ar[j] == i):
				ar[j], ar[i] = ar[i], ar[j]

	# Iterate over array
	for i in range(n):
		
		# If not present
		if (ar[i] != i):
			ar[i] = -1

	# Print the output
	print("Array after Rearranging")

	for i in range(n):
		print(ar[i], end = " ")

# Driver Code
ar = [ -1, -1, 6, 1, 9, 3, 2, -1, 4, -1 ]
n = len(ar)

# Function Call
fixArray(ar, n);

Program:6

Move all zeroes to end of array

Example: 
 
Input :  arr[] = {1, 2, 0, 4, 3, 0, 5, 0};
Output : arr[] = {1, 2, 4, 3, 5, 0, 0, 0};

Input : arr[]  = {1, 2, 0, 0, 0, 3, 6};
Output : arr[] = {1, 2, 3, 6, 0, 0, 0};



/* Java program to push zeroes to back of array */
import java.io.*;
 
class PushZero_right
{
    // Function which pushes all zeros to end of an array.
    static void pushZerosToEnd(int arr[], int n)
    {
        int count = 0;  // Count of non-zero elements
 
        // Traverse the array. If element encountered is
        // non-zero, then replace the element at index 'count'
        // with this element
        for (int i = 0; i < n; i++)
            if (arr[i] != 0)
                arr[count++] = arr[i]; // here count is
                                       // incremented
 
        // Now all non-zero elements have been shifted to
        // front and 'count' is set as index of first 0.
        // Make all elements 0 from count to end.
        while (count < n)
            arr[count++] = 0;
    }
 
    /*Driver function to check for above functions*/
    public static void main (String[] args)
    {
        int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};
        int n = arr.length;
        pushZerosToEnd(arr, n);
        System.out.println("Array after pushing zeros to the back: ");
        for (int i=0; i<n; i++)
            System.out.print(arr[i]+" ");
    }
}

Python:

# Python Program to move all zeros to the end
A = [5, 6, 0, 4, 6, 0, 9, 0, 8]
n = len(A)
j = 0
for i in range(n):
	if A[i] != 0:
		A[j], A[i] = A[i], A[j] # Partitioning the array
		j += 1
print(A) # Print the array