A swap means removing any element from the array and appending it to the back of the same array. Given an array of integers find the minimum number of swaps needed to sort the array.
Example :
A[3]= 3 , 2 , 1
B[3]= 1, 2, 3
i=0 j=0
A[0]!=B[0]
So swap ++ ( Whenever you increment assume that A[i] is removed and appended at the end )
i++
Now i=1 j=0
A[1]!=B[0]
So swap++
i++
Now i=2 j=0
A[2]==B[0]
Now j++
i == n now and hence break the loop
No. of swaps = 2
http://www.spoj.com/problems/MAXSUB/
This one though looks like a complicated problem invoiving many cases , can actually be broken down into just 3 cases
1. All numbers are negative
2. At least one number is 0 but there is no number >0
3. There is at least one number >0
In first case, the best possible sum is the largest number. The number of possibilities is the number of times that number appears in the arrray.
In second case, the best possible sum is 0. The number of possibilities is 2^K – 1 where K is the number of zeros in the array.
In the third case, the best possible sum is the sum of all positive numbers in the array. Number of possibilities is 2^K where K is the number of zeros in the array.
| #include<iostream> | |
| #include<cstdio> | |
| #include<deque> | |
| #include<algorithm> | |
| #include<math.h> | |
| #define MOD 1000000009 | |
| using namespace std; | |
| typedef long long int L; | |
| int main(){ | |
| int t; | |
| L n; | |
| scanf("%d",&t); | |
| while(t--){ | |
| scanf("%lld",&n); | |
| L arr[51000],sum=0LL; | |
| L cnt=1LL; | |
| L zeroCount=0LL; | |
| int allNegative=1; | |
| for(int i=0;i<n;i++){ | |
| scanf("%lld",&arr[i]); | |
| if(arr[i]>0){ | |
| sum+=(long long)arr[i]; | |
| allNegative=0; | |
| } | |
| else if(arr[i]==0){ | |
| allNegative=0; | |
| zeroCount++; | |
| } | |
| } | |
| sort(arr,arr+n); | |
| if(sum==0){//this is to check if there is no +ve num | |
| if(allNegative==1){//if array contains only -ve numbers | |
| sum=arr[n-1]; | |
| for(int j=n-2;j>=0;j--){ | |
| if(sum==arr[j]) | |
| cnt++; | |
| else | |
| break; | |
| } | |
| }else{//if there exist 0's | |
| L num=1; | |
| for(L k=0;k<zeroCount;k++){ | |
| num=(L)(num*2)%MOD;// num of subset is 2^zeroCount-1 | |
| }//decrementing 1 from 2^zeroCount since we should exclude null set according to the prob | |
| cnt=num-1; | |
| } | |
| } | |
| else{//if the array contains +ve numbers | |
| L num=1; | |
| for(L k=0;k<zeroCount;k++){ | |
| num=(L)(num*2)%MOD;// num of subset is 2^zeroCount | |
| } | |
| cnt=num; | |
| } | |
| cnt=cnt%MOD; | |
| printf("%lld %lld\n",sum,cnt); | |
| } | |
| } |
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;
}
Define a macro as shown in line 3 in the code
#include<iostream>
using namespace std;
#define mysizeof(data) (char*)(&data+1)-(char*)(&data)
int main(){
char arr[]={1,2,3};
int arr1[]={1,2,3};
cout<<mysizeof(arr);
cout<<endl<<mysizeof(arr1);
}
output:
3
12
suppose memory location for arr1[] starts with 2000, then arr1[]+1 will point to 2012 and not 2004.
This is because arr1[] is referring to the complete array and hence arr1[]+1 will refer to a memory location just next to the last element of the array.
So, the output with mysizeof(arr1) gives you 12
source:careercup,com
Start two pointers i & j from the end of the string.
a. Keep copying the character from ith location to the jth location and decrement both i & j
b. When i encounters a space, decrement i, but not j
c Repeat steps a & b until i falls of the beginning of the string.
d. Keep setting ‘space’ character at jth location and decrement j unitl j falls of the beginning of the string
source:careercup.com
| /* | |
| * 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; | |
| } | |
Method 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)
I have an array of numbers from 1 to 100 (both inclusive). The size of the array is 100. The numbers are randomly added to the array, but there is one random empty slot in the array. What is the quickest way to find that slot as well as the number that should be put in the slot?
Solution:
Add n=100 elements using n*(n+1)/2 and subtract the sum of the array from it .you will find the missing element
The empty slot can be detected during the iteration in which the sum is computed.
source:stackoverflow
// will be the sum of the numbers in the array.
int sum = 0;
int idx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
idx = i;
} else {
sum += arr[i];
}
}
// the total sum of numbers between 1 and arr.length.
int total = (arr.length + 1) * arr.length / 2;
System.out.println("missing number is: " + (total - sum) + " at index " + idx);find 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)
time complexity O(n^2)
[gist https://gist.github.com/vishnujayvel/5944352]Basically using a sorted array, for each number (target) in an array, you use two pointers, one starting from the front and one starting from the back of the array, check if the sum of the elements pointed to by the pointers is >, < or == to the target, and advance the pointers accordingly or return true if the target is found.
coding hangover 