Codeforces #266 (Div 2) – Number of Ways

Problem link : http://codeforces.com/contest/466/problem/C

Logic:

Let sum of elements in array = S

If S%3==0 then the array cannot be divided into 3 equal parts . So print zero.

Otherwise,

Have a count array where count[i]=number of subarrays in arr[i…n] whose sum is equal to S/3

Now iterate from the first element and add elements to a variable called “temp”

At iteration i, if temp==S/3 then we have found first part of the “3 equal parts array”.count[i+2] will give you the number of ways the rest of the 2 equal parts of the array could be arranged.

The logic here is “if arr[0…i] sums upto S/3 and if arr[i+j…n] sums upto S/3 then inbetween elements arr[i+1…j-1] will also sum upto S/3 ” here j varies from 2 to n-2.

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 10000005
	typedef long long int ll;
	int arr[1000005];
	int count1[1000005];
	int main(){
	int n;
	cin>>n;
	ll s=0;
	REP(i,n){
	cin>>arr[i];
	s+=arr[i];
	}
	if(s%3!=0){
	cout<<"0";
	return 0;
	}
	ll sum=s/3;
	ll temp=0;
	for(int i=n-1;i>=0;i--){
	temp+=arr[i];
	if(temp==sum){
	count1[i]+=1;
	}
	}
	for(int i=n-2;i>=0;i--){
	count1[i]+=count1[i+1];
	}
	temp=0;
	ll ans=0;
	for(int i=0;i+2<n;i++){
	temp+=arr[i];
	if(temp==sum){
	ans+=count1[i+2];
	}
	}
	cout<<ans;
	}

view raw TheNumberOfWays.cpp hosted with ❤ by GitHub

Maximum complete level of a binary tree

Given a binary tree, find the maximum level at which tree is completely filled.

	int getMaxCompleteLevel(node* node){
	if(node==NULL||!(node->left)||!(node->right))
	return 0;
	int l=getMaxCompleteLevel(node->left);
	int r=getMaxCompleteLevel(node->right);
	return 1+min(l,r);
	}

view raw getMaxCompleteLevel.cpp hosted with ❤ by GitHub

Sorting an array of 0’s , 1’s and 2’s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

The problem was posed with three colours, here `0′, `1′ and `2′. The array is divided into four sections:

1. a[1..Lo-1] zeroes (red)
2. a[Lo..Mid-] ones (white)
3. a[Mid..Hi] unknown
4. a[Hi+1..N] twos (blue)

Three flags should be used for pointing the last of 0, the last of 1, and the first of 2.

 

The unknown region is shrunk while maintaining these conditions

1. Lo := 1; Mid := 1; Hi := N;
2. while Mid <= Hi do
   1. Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and a[Hi+1..N]=2; a[Mid..Hi] are unknown.
   2. case a[Mid] in
      • 0: swap a[Lo] and a[Mid]; Lo++; Mid++
      • 1: Mid++
      • 2: swap a[Mid] and a[Hi]; Hi–

[gist https://gist.github.com/vishnujayvel/6050043]

 

source: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Flag/

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)

	/*
	* 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;
	}

view raw findmaxidexdiff.cpp hosted with ❤ by GitHub

Find the two repeating elements in a given array

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)

Given an array of numbers, find out if 3 of them add up to 0

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.