bool findElement(int a[], int length, int expectedNum)
{
int i = 0;
while(i < length)
{
if(a[i] == expectedNum)
return true;
else
{
int diff = abs(expectedNum - a[i]);
i = diff + i;
}
}
return false;
}
Category Archives: arrays
Given an array of length N containing integers between 1 and N, determine if it contains any duplicates in O(n) time complexity and O(1) space complexity
0Since we cannot use extra space, take advantage of the fact that the array has elements only from 1 to n
and there are n elements in the array(index ranges from 0 to n-1)
So if 1 occurs make value at 0th index negative
if 2 occurs make the value at 1st index negative
if n occurs make the value at n-1th index negative
So if the same number occurs again then the value at that number index will be found negative already and
voila !Thus we found a way finding repeating number.
Algorithm
traverse the list for i= 0 to n-1 elements
{
check for sign of A[abs(A[i])] ;
if positive then
make it negative by A[abs(A[i])]=-A[abs(A[i])];
else // i.e., A[abs(A[i])] is negative
this element (ith element of list) is a repetition
}
Given an Array A[], find the maximum j – i such that A[j] > A[i]. For example Input { 34,8,10,3,2,80,30,33,1} and Output 6 (j=7, i=1) Time Complexity should be less then O(n^2)
0
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /* | |
| * Given an array arr[], find the maximum j – i such that arr[j] > arr[i] | |
| * | |
| * Solution : | |
| * Create 2 arrays | |
| * 1)LeftMin : stores the minimum element to the left of arr[i] including arr[i] | |
| * 2)RightMax : stores the maximum element to the right of arr[i] including arr[i] | |
| * Initialize maxDiff=-1 | |
| * Create a loop comparing leftMin[i] and RightMax[j] starting with i=0 and j=0 till i or j reaches n | |
| * If LeftMin[i]>RightMax[j]{ | |
| maxDiff=max(maxDiff,j-i) | |
| * j++ | |
| * } | |
| * else | |
| * i++ | |
| * | |
| * maxDiff holds the maximum j-i | |
| */ | |
| #include<iostream> | |
| using namespace std; | |
| int max(int a,int b){ | |
| if(a>b) | |
| return a; | |
| else | |
| return b; | |
| } | |
| int min(int a,int b){ | |
| if(a>b) | |
| return b; | |
| else | |
| return a; | |
| } | |
| int findMaxDiff(int arr[],int n){ | |
| int LeftMin[n]; | |
| int RightMax[n]; | |
| LeftMin[0]=arr[0]; | |
| for(int i=1;i<n;i++) | |
| LeftMin[i]=min(LeftMin[i-1],arr[i]); | |
| RightMax[n-1]=arr[n-1]; | |
| for(int i=n-2;i>=0;i--) | |
| RightMax[i]=max(RightMax[i+1],arr[i]); | |
| int i=0; | |
| int j=0; | |
| int maxDiff=-1; | |
| while(i<n&&j<n){ | |
| if(LeftMin[i]<RightMax[j]){ | |
| maxDiff=max(maxDiff,j-i); | |
| j++; | |
| } | |
| else | |
| i++; | |
| } | |
| return maxDiff; | |
| } | |
| int main(){ | |
| int arr[]={34, 8, 10, 3, 2, 80, 30, 33, 1}; | |
| int n = sizeof(arr)/sizeof(arr[0]); | |
| int maxDiff = findMaxDiff(arr, n); | |
| cout<<maxDiff; | |
| return 0; | |
| } | |
You are given an array of n integers which can contain integers from 1 to n only . Some elements can be repeated multiple times and some other elements can be absent from the array . Write a running code on paper which takes O(1) space apart from the input array and O(n) time to print which elements are not present in the array and the count of every element which is there in the array along with the element number .
0Time complexity : O(n)
Space complexity: O(1)
We implement count sort technique to get the frequency of the elements 1 to n
[gist https://gist.github.com/vishnujayvel/5998457]Find the two repeating elements in a given array
0Method 1:(creating BST)
This can be done in O(nlogn) by inserting the elements(worst case:insert all n elements to find the 2 duplicates) into a BST and to check for duplicate elements.
Method 2:(creating count array)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.
Time complexity: O(n)
Balance index of an array
0find the balance index of an array where balanced index i is defined as the one whose left sum is equal to the right sum of the index .
i.e
summation (1 to i-1) = summation (i+1 to length of an array)
Find a sorted subsequence of size 3 in linear time
0Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If there are multiple such triplets, then print any one of them.
Examples:
Input: arr[] = {12, 11, 10, 5, 6, 2, 30}
Output: 5, 6, 30
Input: arr[] = {1, 2, 3, 4}
Output: 1, 2, 3 OR 1, 2, 4 OR 2, 3, 4
Input: arr[] = {4, 3, 2, 1}
Output: No such triplet
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream>
using namespace std;
void findSubsequence(int arr[],int n){
int max=n-1;
int min=0;
int *larger=new int[n];
int *smaller=new int[n];
//store the index of the element smaller than arr[i] (on its left side)
//in smaller[i] or -1 if there is no such element
smaller[0]=-1;//its obvious since theres no element in the left of arr[0]
for(int i=1;i<n;i++ ){
if(arr[i]>arr[min]){
smaller[i]=min;
}
else{
smaller[i]=-1;
min=i;
}
}
//store the index of the element larger than arr[i] (on its right)
//in larger[i] or -1 if there is no such element
larger[n-1]=-1;//since theres no element in the right of arr[n-1]
for(int i=n-2;i>=0;i--){
if(arr[i]<arr[max]){
larger[i]=max;
}
else{
larger[i]=-1;
max=i;
}
}
//find the first number which has smaller element on its left and larger element
//on its right
for(int i=0;i<n;i++){
if(smaller[i]!=-1&&larger[i]!=-1){
cout<<endl<<arr[smaller[i]]<<' '<<arr[i]<<' '<<arr[larger[i]];
return;
}
}
cout<<"NO such triplet";
return;
}
int main(){
int arr[]={34,56,45,51,69,70};
findSubsequence(arr,6);
}
coding hangover 