array data structure
Fibonacci series
#include<stdio.h>
int fib(int n)
{
/* Declare an array to store Fibonacci numbers. */
int f[n+2]; // 1 extra to handle case, n = 0
int i;
/* 0th and 1st number of the series are 0 and 1*/
f[0] = 0;
f[1] = 1;
for (i = 2; i <= n; i++)
{
/* Add the previous 2 numbers in the series
and store it */
f[i] = f[i-1] + f[i-2];
}
return f[n];
}
int main ()
{
int n = 9;
printf("%d", fib(n));
getchar();
return 0;
}
1.Find the missing number .there is no duplicates in the list of n-1 number continuous number.
import java.io.*;
class GFG
{
public static void main (String[] args)
{
int[] a={1,2,3,4,5,7,8};
int n=a.length;
int p=0;
for(int i=0;i<n;i++)
{
p=p+a[i];
}
int missing=n*(n+1)/2 -p;
System.out.println(missing);
}
}
2.find the duplicates in o(n) and= space o()
import java.io.*;
class GFG {
public static void main (String[] args)
{
int a[]={2,3,4,6,4,5,6,7};
int k=a.length;
int i=0;
for(i=0;i<k;i++)
{
if(a[i]>0)
{
a[a[i]]=-a[a[i]];
}
else
{
System.out.println(Math.abs(a[i])) ;
}
}
}
3.find the number which occur odd number of times O(n) space .
import java.io.*;
import java.util.*;
class GFG {
public static void main (String[] args)
{
int a[]={1,2,3,1,2,3,5,6,6};
int p=0;
for(int i=0;i<a.length;i++)
{
p=p ^ a[i];
}
System.out.print(p);
}
}
4.find two repeating element in array.//Use array elements as index)
class GFG
{
public static void main (String[] args)
{
int a[]={1,2,1,2,3,4,1};
int p=0;
for(int i=0;i<a.length;i++)
{
if(a[Math.abs(a[i])]>0)
{
a[Math.abs(a[i])]=-a[Math.abs(a[i])];
}
else
{
System.out.println(Math.abs(a[i]));
}
}
}
}
5.find two element in array whose sum equal to k. O(n) space :O(1)
import java.io.*;
import java.util.*;
class GFG {
static void fun(int[] a,int k)
{
Arrays.sort(a);
int j=a.length-1;
int i=0;
while(i<j)
{
int sum=a[i] + a[j];
if(sum==k)
{
System.out.print(true+","+a[i]+","+a[j]);
return;
}
else if(sum > k)
{
j--;
}
else
{
i++;
}
}
System.out.print("No");
}
public static void main (String[] args)
{
int a[]={1,2,3,-8,5,7,4};
fun(a,-6);
}
}
Note :To find xor of two number
int a=5,b=10;
int a=5,b=10;
System.out.print((a|b) & (-a | -b)); //formula of xor
6.find the unique element if apart from unique element all are repeated three times.
import java.io.*;
class GFG {
public static void main (String[] args) {
int[] a={1,2,1,2,3,3,1,2,3,5};
int ones=0,twos=0,commonbit=0;
for(int i=0;i<a.length;i++)
{
twos=twos | (ones & a[i]);
ones=ones ^ a[i];
commonbit=~(ones & twos);
ones = ones & commonbit;
twos = twos & commonbit;
}
System.out.println(ones);
}
}
7. Find two element whose sum is closest to zero.
import java.io.*;
import java.util.*;
class GFG {
public static void main (String[] args)
{
int i=0,positiveClosest=Integer.MAX_VALUE,negativeValue=Integer.MIN_VALUE;
int[] a={1,2,3,5,-4};
int j=a.length-1;
Arrays.sort(a);
int temp=a[i]+a[j],sum=0;
int t=0;
while(i<j)
{
t=0;
sum=a[i]+a[j-1];
if(Math.abs(temp)>=Math.abs(sum)) //going nearest to 0
{
temp=sum;
j--;
t=1;
}
sum=a[i+1]+a[j];
if(Math.abs(temp)>=Math.abs(sum))//after increasing value of i going toward 0
{
temp=sum;
i++;
t=1;
}
if(t!=1)
{
break;
}
}
System.out.print(temp+","+a[i]+","+a[j]);
}
}
8.find element in sorted rotated array. O(logn)
class Main
{
// Returns index of key in arr[l..h]
// if key is present, otherwise returns -1
static int search(int arr[], int l, int h, int key)
{
if (l > h)
return -1;
int mid = (l+h)/2;
if (arr[mid] == key)
return mid;
/* If arr[l...mid] is sorted */
if (arr[l] <= arr[mid])
{
/* As this subarray is sorted, we
can quickly check if key lies in
half or other half */
if (key >= arr[l] && key <= arr[mid])
return search(arr, l, mid-1, key);
return search(arr, mid+1, h, key);
}
/* If arr[l..mid] is not sorted,
then arr[mid... r] must be sorted*/
if (key >= arr[mid] && key <= arr[h])
return search(arr, mid+1, h, key);
return search(arr, l, mid-1, key);
}
//main function
public static void main(String args[])
{
int arr[] = {4, 5, 6, 7, 8, 9, 1, 2, 3};
int n = arr.length;
int key = 3;
int i = search(arr, 0, n-1, key);
if (i != -1)
System.out.println("Index: " + i);
else
System.out.println("Key not found");
}
}
Output:
Index:8
9.Search the Pivot Index in rotated array.
import java.io.*;
import java.util.*;
class gfg
{
static int search(int[] a,int start,int finish)
{
if(start-finish==0)
{
return start;
}
else if(start==finish -1)
{
if(a[start]>=a[finish])
{
return start;
}
else
{
return finish;
}
}
else
{
int mid=(start + finish)/2;
if(a[start]>=a[mid])
{
return search(a,start,mid);
}
else
{
return search(a,mid,finish);
}
}
}
public static void main(String[] args)
{
int[] a={3,4,5,6,1,2};
int n=a.length;
int k=search(a,0,n-1);
System.out.print(k);
}
}
10.Given a sorted array ,possibly with duplicates .find the number of occurrences of a number.
Find the left and right of indexes and calculate right -left +1
import java.io.*;
import java.util.*;
class GFG
{
public static int fun(int[] a,int l,int h,int key)
{
int a1=first(a,l,h,key);
int b1=last(a,l,h,key);
return b1-a1 + 1;
}
public static int first(int[] a,int l,int h,int key)
{
while(l<=h)
{
int mid=(l+h)/2;
if((mid==l && a[mid]==key ) || (a[mid]==key && a[mid-1]<key))
{ //concept to find part here a[mid-1]<key bcz we r mvng towars left side
return mid;
}
else if(a[mid]>=key)
{
return first(a,l,mid-1,key);
}
else
{
return first(a,mid+1,h,key);
}
}
return -1;
}
public static int last(int[] a,int l,int h, int key)
{
while(l<=h)
{
int mid=(l+h)/2;
if((mid==h && a[mid]==key) || (a[mid]==key && a[mid+1]>key))
{ //concept to find part here a[mid-1]>key bcz we r mvng towars right side
return mid;
}
else if(a[mid]<=key)
{
return last(a,mid+1,h,key);
}
else
{
return last(a,l,mid-1,key);
}
}
return -1;
}
public static void main(String[] args)
{
int[] a={1,1,1,2,2,2,7,8,8};
int n=a.length;
System.out.print(fun(a,0,n-1,8));
}
}
Note:majority element means element which occur more than n/2 times.
12.check majority element . time :O(n) space:O(1)
printMajority (a[], size)
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "No Majority Element"
1. Find the candidate for majority
2. If candidate is majority. i.e., appears more than n/2 times.
Print the candidate
3. Else
Print "No Majority Element"
Below is the implementation of the above approach :
/* Program for finding out majority element in an array */
http://youtube.com/watch?v=uwogtyFiDLg&pbjreload=10
import java.io.*;
import java.util.*;
class GFG
{
public static void fun(int[] a)
{
int a1=find_candidate(a);
boolean b1=check_majority(a,a1);
if(b1==true)
System.out.println(b1);
}
public static int find_candidate(int[] a)
{
int count=1;
int majority=a[0];
for(int i=1;i<a.length;i++)
{
if(majority==a[i])
{
count++;
}
else
{
count--;
}
if(count==0)
{
count=1;
majority=a[i];
}
}
return majority; //it will return that which will have majority counter nonZero .till end of traversal.
}
public static boolean check_majority(int[] a,int majority_ele)
{ //checking element occur n/2 or not
int temp=0;
for(int i=0;i<a.length;i++)
{
if(a[i]==majority_ele)
{
temp++;
}
}
if(temp>a.length/2)
{
System.out.println("majority element is: "+majority_ele);
return true;
}
else
{
System.out.print("No majority element");
return false;
}
}
public static void main(String[] args)
{
int[] a={1,1,2,2,2,7,8,8,8};
int n=a.length;
fun(a);
}
}
13.Separate/segregate even and odd.
Given an array A[], write a program that segregates even and odd numbers. The program should put all even numbers first in sorted order, and then odd numbers in sorted order
import java.io.*;
import java.util.*;
class GFG
{
public static void get(int[] ar)
{
int p=-1;
for(int i=0;i<ar.length;i++) // from here i m tring to bring all even on left side
{
if(ar[i] %2 ==0)
{
p++;
int temp=ar[i];
ar[i]=ar[p];
ar[p]=temp;
}
}
for(int i=0;i<ar.length;i++) //to sort the left and right part getting index
{
if(ar[i] %2 !=0)
{
p=i;
break;
}
}
if(p>0)
{
Arrays.sort(ar,0,p);
}
Arrays.sort(ar,p,ar.length);
// print(ar);
}
public static void main(String[] args)
{
int[] a={10,2,3,4,5,0,1,23,4};
get(a,a.length);
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
}
}
Alternate solution
static void segregateEvenOdd(int arr[])
{
/* Initialize left and right indexes */
int left = 0, right = arr.length - 1;
while (left < right)
{
/* Increment left index while we see 0 at left */
while (arr[left]%2 == 0 && left < right)
left++;
/* Decrement right index while we see 1 at right */
while (arr[right]%2 == 1 && left < right)
right--;
if (left < right)
{
/* Swap arr[left] and arr[right]*/
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
}
//in last do soting for both part
12 34 45 9 8 90 3
Output:
8 12 34 90 3 9 45 // sorted in left and right
13.Sort 0,1,2 in order of n ………...O(n) nd space O(1)
import java.io.*;
class GFG
{
public static void fun(int[] a)
{
int low=0,mid=0,high=a.length-1;
int temp=0;
while(mid<=high)
{
switch(a[mid])
{
case 0:
temp=a[low];
a[low]=a[mid];
a[mid]=temp;
low++;mid++;
break ;
case 1:
mid++;
break;
case 2:
temp=a[mid];
a[mid]=a[high];
a[high]=temp;
high--;
break;
}
}
}
public static void main(String[] args)
{
int[] a={0,1,2,1,1,1,2,2,1};
fun(a);
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");
}
}
}
Output:
0 1 1 1 1 1 2 2 2
14.Maximum difference between two elements such that larger element appears after the smaller number.
import java.io.*;
import java.util.*;
class GFG
{
public static void fun(int[] a,int n)
{
int min_diff=a[0],diff=0,max_diff=0;
for(int i=1;i<a.length;i++)
{
diff=a[i]-min_diff;
if(diff>max_diff)
{
max_diff=diff;
}
if(min_diff>a[i])
{
//int temp=min_diff;
min_diff=a[i];
}
}
System.out.print(max_diff);
}
public static void main(String[] args)
{
int[] a={10,2,3,4,5,0,1,23,4};
fun(a,a.length);
}
}
Note: calculate no. of zeros trailing in n!.
public static void fun(int n)
{
int count=0;
for(int i=5;n/i>0;i*=5)
{
count+=n/i;
}
System.out.print(count);
}
15.Max sub array from array
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
static public void ping(int[] ar,int t)
{
int sum=ar[0];
int current=0;
int start=0,end=0,s=0;
for(int i=0;i<t;i++)
{
current=current + ar[i];
if(current>sum)
{
sum=current;
start=s; end=i;
}
if(current<0)
{
current=0;
s=i+1;
}
}
System.out.println(sum+" ,"+start+","+end);
}
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
for(int i=0;i<a;i++)
{
int a1=sc.nextInt();
int[] ar=new int[a1];
for(int j=0;j<a1;j++)
{
ar[j]=sc.nextInt();
}
ping(ar,a1);
}
}
}
For Input:
2
3
1 2 3
4
-1 -2 -3 -4
Your Output is:
6 ,0,2
-1 ,0,0
2
3
1 2 3
4
-1 -2 -3 -4
Your Output is:
6 ,0,2
-1 ,0,0
16.Equilibrium index of an array.
static void print(int[] a,int n)
{
int sum=0,curr_sum=0;
for(int i=0;i<n;i++)
{
sum=sum + a[i];
}
for(int i=0;i<n;i++)
{
curr_sum=curr_sum+a[i];
if(curr_sum==sum)
{
System.out.println(i+1);
return;
}
sum=sum-a[i];
}
System.out.println("-1");
return;
}
/*
Input : A[] = {-7, 1, 5, 2, -4, 3, 6}
Output : 3
3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
Output : 3
3 is an equilibrium index, because:
A[0] + A[1] + A[2] = A[4] + A[5] + A[6]
*/
Count the number of ways to tile the floor of size n x m using 1 x m size tiles
| 1, 1 < = n < m
count(n) = | 2, n = m
| count(n-1) + count(n-m), m < n
count(n) = | 2, n = m
| count(n-1) + count(n-m), m < n
solution:
// Java implementation to count number
// of ways to tile a floor of size
// n x m using 1 x m tiles
import java.io.*;
class GFG {
// function to count the total number of ways
static int countWays(int n, int m)
{
// table to store values
// of subproblems
int count[] = new int[n + 1];
count[0] = 0;
// Fill the table upto value n
int i;
for (i = 1; i <= n; i++) {
// recurrence relation
if (i > m)
count[i] = count[i - 1] + count[i - m];
// base cases
else if (i < m)
count[i] = 1;
// i = = m
else
count[i] = 2;
}
// required number of ways
return count[n];
}
// Driver program
public static void main(String[] args)
{
int n = 7;
int m = 4;
System.out.println("Number of ways = "
+ countWays(n, m));
}
}
// This code is contributed by vt_m.
Search a 2D Matrix
Input : mat[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 29
Output : Found at (2, 1)
Input : mat[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 100
Output : Element not found
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 29
Output : Found at (2, 1)
Input : mat[4][4] = { {10, 20, 30, 40},
{15, 25, 35, 45},
{27, 29, 37, 48},
{32, 33, 39, 50}};
x = 100
Output : Element not found
class Solution {
public boolean searchMatrix(int[][] matrix, int target)
{
if(matrix.length==0) return false;
int row=matrix.length;
int column=matrix[0].length;
int i=0;
int j=column-1;
while(i<row && j>=0)
{
if(matrix[i][j]==target)
{
return true;
}
else if(matrix[i][j]<target)
{
i++;
}
else if(matrix[i][j]>target)
{
j--;
}
}
}
}O(n)+O(m)
/*
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix==null || matrix.length<1 || matrix[0].length<1) return false;
return binarySearch(matrix,0,0,matrix.length-1,matrix[0].length-1,target);
}
public static boolean binarySearch(int[][] matrix,int lx,int ly,int hx,int hy,int target)
{
if(lx>hx || ly>hy) return false;
if(target<matrix[lx][ly] || target>matrix[hx][hy]) return false;
int mx=(lx+hx)/2;
int my=(ly+hy)/2;
if(target>matrix[mx][my])
{
return binarySearch(matrix,mx+1,ly,hx,my,target) || binarySearch(matrix,lx,my+1,hx,hy,target);
}
else if(target<matrix[mx][my])
{
return binarySearch(matrix,lx,ly,hx,my-1,target) || binarySearch(matrix,lx,my,mx-1,hy,target);
}
else
return true;
}
}
*/complixty:O(logn +log(m))
Kth Largest Element in an Array
public int findKthLargest(int[] nums, int k) {
final int N = nums.length;
Arrays.sort(nums);
return nums[N - k];
}
final int N = nums.length;
Arrays.sort(nums);
return nums[N - k];
}
public int findKthLargest(int[] nums, int k) {
final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
pq.offer(val);
if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
final PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int val : nums) {
pq.offer(val);
if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
Best method: quick sort select O(n)
Factorials of large numbers
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
class FacorialOfBigNuumber
{
public static void main (String[] args) throws java.lang.Exception
{
BigInteger fact= BigInteger.ONE;
int factorialNo = 100;
for (int i = 2; i <= factorialNo; i++)
{
fact = fact.multiply(new BigInteger(String.valueOf(i)));
}
System.out.println("The factorial of " + factorialNo +" is: " + fact);
}
}
import java.lang.*;
import java.io.*;
import java.math.*;
class FacorialOfBigNuumber
{
public static void main (String[] args) throws java.lang.Exception
{
BigInteger fact= BigInteger.ONE;
int factorialNo = 100;
for (int i = 2; i <= factorialNo; i++)
{
fact = fact.multiply(new BigInteger(String.valueOf(i)));
}
System.out.println("The factorial of " + factorialNo +" is: " + fact);
}
}
Concept to reverse a number
int n=sc.nextInt();
int rev=0;
while(n>0)
{
rev=rev*10 + n%10;
n=n/10;
}
Count numbers divisible by M
public static void main (String[] args)
{
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
for(int i=0;i<t;i++)
{
int a=sc.nextInt(); //first number
int b=sc.nextInt();//second number
int m=sc.nextInt(); //divisible by m
if(a%m==0)
{
System.out.println(b/m -a/m +1);
}
else
{
System.out.println(b/m -a/m);
}
}
}
Add Binary string
This program is to print pyramid/triangle number pattern 21 in C.
1
2 1 2
3 2 1 2 3
4 3 2 1 2 3 4
5 4 3 2 1 2 3 4 5
6 5 4 3 2 1 2 3 4 5 6
7 6 5 4 3 2 1 2 3 4 5 6 7
This program is to print pyramid/triangle number pattern 22 in C.
1
121
12321
1234321
123454321
12345654321
1234567654321
sorting
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Output: [0,0,1,1,2,2]
Divide array into two sub-arrays such that their averages are equal
Input : arr[] = {1, 5, 7, 2, 0};
Output : (0 1) and (2 4)
Subarrays arr[0..1] and arr[2..4] have
same average.
Output : (0 1) and (2 4)
Subarrays arr[0..1] and arr[2..4] have
same average.
Maximum sum such that no two elements are adjacent. follows a rule while looting the houses and according to the rule he will never loot two consecutive houses.
Generate all subsequence
there are 15 sub-sequences. They are (1), (2), (3), (4), (1,2), (1,3),(1,4), (2,3), (2,4), (3,4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). More generally, we can say that for a sequence of size n, we can have (2^n - 1) non-empty sub-sequences in total.
Multiplication of two matrix:
Check Matrix is orthogonal or not
Longest subarray whose sum equals to 0.
Largest subarray with equal number of 0s and 1s
update 0 with -1 question will become same
Count all subarray whose sum equals to k
Maximum Product Subarray
Subarray Product Less Than K
Count product of all subarray whose product equals to k.
Count pairs with given sum
This solution is for non repeating element and sorted array.
O(n^2 solution)
General Solution O(n)
Putting all element to 1 if non repeating else count +1
Calculating pair for every element now we have to print count / 2
Find all pairs with a given sum if two array is given
Input : A[] = {1, 2, 4, 5, 7}
B[] = {5, 6, 3, 4, 8}
x = 9
Output : 1 8, 4 5, 5 4
B[] = {5, 6, 3, 4, 8}
x = 9
Output : 1 8, 4 5, 5 4
Binary Search(w/o recursion)https://youtu.be/OE7wUUpJw6I?list=PL2_aWCzGMAwL3ldWlrii6YeLszojgH77j
First and last occurence of a number in binary search
Below concept is to find first index .
To get last index just edit //////
if(x==mid)
{ result<--mid; low=mid+1;}
How many times is a sorted array rotated?
Its for array having no duplicate .
Search element in a circular sorted array
Its for array having no duplicate .
Count a element in array
Print matrix in spiral order
Check for balanced parentheses using stack
Comments
Post a Comment