Google Interview Question
Country: United States
This is the solution I gave and interviewer was expecting the same, although needed a small hint.
int
count_pairs_ge(int *A, int size, int N)
{
int i;
int count = 0;
for (i = 0; i < size-1; i++) {
if ((A[i] + A[size-1]) < N)
continue;
if ((A[i] + A[i+1]) >= N)
break;
/* this element A[i] is a possibility */
for (int j = i+1; j < size; j++) {
if (A[i] + A[j] >= N)
count++;
}
}
if (i != size) {
int x = size - i;
if (x >= 2)
count += (x-1)*(x)/2;
}
printf("N=%d, count=%d\n", N, count);
return count;
}
1. iterate array
2. create a flag to check how many numbers to the right got a sum greater or equal to given n.
3. move that flag to the left according to given condition
public static void main(String[] args) {
// TODO Auto-generated method stub
//int[] array = {1, 2, 3, 4, 5, 6, 9, 11};
// 3, 11
// 4, 11
// 5, 11
// 5, 9
// 6, 11
// 6, 9
// 9, 11
//int[] array = {1, 2, 3, 4, 5, 6};
// No sums
int[] array = {3, 7, 8, 10};
// 7, 8
// 7, 10
// 8, 10
int n = 14;
System.out.println(findCountofNumbers(array, n));
}
static int findCountofNumbers(int[] array, int n) {
int count = 0;
int minForN = array.length-1;
for (int i = 0; i < array.length; i++) {
// check prev numbers until sum of 2 elements of the array is less than n
while(array[i] + array[minForN] >= n && minForN >= 0 && n != minForN) {
minForN--;
}
if (i < minForN)
count += array.length - 1 - minForN;
else
count += array.length - 1 - i;
}
return count;
}
Nice O(n) solution !
You might want to change the order of conditions in while expression.
I was getting a ArrayOutOfBound Exception for array[minForN] with minForN = -1
Complexity O(n) and Memory O(1):
since the array is sorted A[i] + A[j] > val => A[i] + A[j+c] > val
we can use a left index and right index that move towards each other to compute this value
public static int getCountCombsGreater(int[] arr, int val){
int count = 0;
int left = 0;
int right = arr.length -1;
while(left < right){
//while the left index should be moved
while(arr[left] + arr[right] < val && left < right){
left++;
}
if(left < right){
count += arr.length - right;
}
right--;
while(right-1 > left && arr[right] == arr[right-1]){
right --;
}
}
return count;
}
Should the two numbers be different ?
for ex : [1,3,5,6,7] and n is 6
3,3 or any 5,5 can be consider a count?
Hi,
If the array is sorted...with a little bit of simple math wouldn't the count of sums that are greater than N be finding the first number that is >= N/2 and after that number all the numbers sum is greater than N?
Say X numbers with any 2 summed being greater than or equal to N => combinations of X by 2(formula).
Complexity: XlogN
#include <iostream>
#include <map>
using namespace std;
int main() {
int n,k,a,cnt = 0;
map<int,int> mymap;
map<int,int>::iterator it;
cin>>n>>k;
for( int i = 0 ; i < n ; i++ ){
cin>>a;
if( mymap.find(a) != mymap.end() )
mymap[a]++;
else
mymap[a] = 1;
}
for( it = mymap.begin() ; it != mymap.end() ; it++ ){
int val = it->first;
if( mymap.find(k-val) != mymap.end() ){
cnt += min( it->second, mymap.find(k-val)->second );
it->second = 0;
}
}
cout<<cnt;
return 0;
}
#include <iostream>
#include <map>
using namespace std;
int main() {
int n,k,a,cnt = 0;
map<int,int> mymap;
map<int,int>::iterator it;
cin>>n>>k;
for( int i = 0 ; i < n ; i++ ){
cin>>a;
if( mymap.find(a) != mymap.end() )
mymap[a]++;
else
mymap[a] = 1;
}
for( it = mymap.begin() ; it != mymap.end() ; it++ ){
int val = it->first;
if( mymap.find(k-val) != mymap.end() ){
cnt += min( it->second, mymap.find(k-val)->second );
it->second = 0;
}
}
cout<<cnt;
return 0;
}
Here is my solution
int numberOfPairs(int[] data, int n) {
if (data == null)
throw new NullPointerException();
int count = 0;
int backPointer = data.length - 1;
for (int index = 0; index <backPointer;) {
if ((data[backPointer] + data[index] >= n)) {
count+=backPointer - index ;
System.out.println(data[backPointer] +" "+ data[index]);
backPointer--;
} else
index++;
}
return count;
}
O(n) .. taking advantage of a sorted array, given start and end pointers. if A[start]+A[end]>=n, it implies that all elements at positions > start achieve the condition. That's why we count+=end-start.
public static int count(int [] array, int n){
if(array == null) return 0;
int count=0;
int start=0;
int end=array.length-1;
while(end>start){
if(array[start] + array[end] >= n){
count+= end-start;
end--;
}else{
start++;
}
}
return count;
}
public void sumcount(int n)
{
int size=array1.length;
int lindex=0;
int hindex= size-1;
int mid;
int count=0;
mid= (lindex+hindex)/2;
System.out.println ("value of mid is"+mid);
if (array1[mid]+array1[mid+1]>= n)
{
count=(size-mid)/2 +1;
System.out.println ("count is"+count);
}
while ( mid != 0 && (array1[mid]+array1[mid-1]>=n))
{
count++;
System.out.println ("value of count in while is"+count);
mid--;
System.out.println ("value of mid in while is"+mid);
}
System.out.println ("count is "+ count);
}
}
public void sumcount(int n)
{
int size=array1.length;
int lindex=0;
int hindex= size-1;
int mid;
int count=0;
mid= (lindex+hindex)/2;
System.out.println ("value of mid is"+mid);
if (array1[mid]+array1[mid+1]>= n)
{
count=(size-mid)/2 +1;
System.out.println ("count is"+count);
}
while ( mid != 0 && (array1[mid]+array1[mid-1]>=n))
{
count++;
System.out.println ("value of count in while is"+count);
mid--;
System.out.println ("value of mid in while is"+mid);
}
System.out.println ("count is "+ count);
}
}
public void sumcount(int n)
{
int size=array1.length;
int lindex=0;
int hindex= size-1;
int mid;
int count=0;
mid= (lindex+hindex)/2;
System.out.println ("value of mid is"+mid);
if (array1[mid]+array1[mid+1]>= n)
{
count=(size-mid)/2 +1;
System.out.println ("count is"+count);
}
while ( mid != 0 && (array1[mid]+array1[mid-1]>=n))
{
count++;
System.out.println ("value of count in while is"+count);
mid--;
System.out.println ("value of mid in while is"+mid);
}
System.out.println ("count is "+ count);
}
}
There are two cases here
1) if a number say no in the array is less than n/2 then we need to locate (n - no) or more. Everything after this will add up with no to give a sum >= n.
2) All the numbers >= n/2 will definitely will add up with each other to have a sum > n
Code:
public class Countofsum {
public static void main(String[] args) {
int ar[] = {1,2,3,4,8};
System.out.println(countPairs(ar, 6));
}
public static int countPairs(int ar[], int sum) {
int count = 0, l;
int i;
for (i = 0; i < ar.length-1 && ar[i] < sum / 2; i++) {
l = locate(ar, i + 1, sum - ar[i]);
if (l != -1)
count += ar.length - l;
}
int n = ar.length - 1 - i;
count += (n * (n+1))/2;
return count;
}
public static int locate(int ar[], int st, int no) {
int end = ar.length - 1;
int res = -1;
int mid;
while (st <= end) {
mid = (st + end) / 2;
if (ar[mid] == no)
return mid;
if (ar[mid] > no) {
res = mid;
end = mid - 1;
} else {
st = mid + 1;
}
}
return res;
}
}
Much better O(N) solution:
// 0 1 2 3 4 5 6 7 8 9
// ^ (10 / 2 - 1)
// (0,9), (0,8) 2
// (1,9), (1,8), (1,7), 3
// (2,9), (2,8), (2,7), (2,6), 4
// (3,9), (3,8), (3,7), (3,6), (3,5) 5
// (4,9), (4,8), (4,7), (4,6), (4,5), (4,4) 6
// (5,9), (5,8), (5,7), (5,6), (5,5) 5
// (6,9), (6,8), (6,7), (6,6) 4
// (7,9), (7,8), (7,7) 3
// (8,9), (8,8) 2
// (9,9) 1
// Count = 35
// 0 1 2 3 4 5 6 7 8 9 10
// ^ (11 / 2 - 1)
// (0,10), (0,9), (0,8) 3
// (1,10), (1,9), (1,8), (1,7), 4
// (2,10), (2,9), (2,8), (2,7), (2,6), 5
// (3,10), (3,9), (3,8), (3,7), (3,6), (3,5) 6
// (4,10), (4,9), (4,8), (4,7), (4,6), (4,5), (4,4) 7
// (5,10), (5,9), (5,8), (5,7), (5,6), (5,5) 6
// (6,10), (6,9), (6,8), (6,7), (6,6) 5
// (7,10), (7,9), (7,8), (7,7) 4
// (8,10), (8,9), (8,8) 3
// (9,10), (9,9) 2
// Count = 45
size_t greaterthansumpairs(vector<long>& numbers, long sum)
{
size_t count = 0, count1;
for (size_t it = 0; it <= numbers.size()/2 - 1; it++) {
count1 = 0;
for (size_t rit = numbers.size() - 1; rit >= 0 && numbers[it] + numbers[rit] >= sum && it <= rit; rit--)
count1++;
if (it == 0 && count1 > 0)
count += count1 - 1;
if (it != numbers.size() / 2 - 1)
count1 *= 2;
count += count1;
}
return count;
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication4
{
class Program
{
static void Main(string[] args)
{
var arry =new int[] { 1, 2, 3, 4, 5 };
var res = SumGreaterThanN(arry, 3);
var res2 = SumGreaterThanN(arry, 10);
var res3 = SumGreaterThanN(arry, 7);
}
public static int SumGreaterThanN(int[] arr, int n)
{
if (arr == null || arr.Length <= 1)
{
return 0;
}
var m1 = arr[1] + arr[0] > n ? 1 : 0;
// unexplored elements [0..k1]
var u1 = m1 == 0 ? 1 : -1;
for (int i = 2; i < arr.Length; i++)
{
// -:) pairs will work if a[i] is replaced by a[i-1]
m1 += i - (u1 + 1);
while (u1 >= 0)
{
if (arr[i] + arr[u1] > n)
{
m1++;
u1--;
}
else
{
break;
}
}
if (arr[i] + arr[i - 1] < n)
{
u1 = i;
}
}
return m1;
}
}
}
Given an exmaple A= {1,2,3,4,5,6} and n = 10. Keep start and end pointer. When A[start] + A[end] >= n then all elements from start, start+1, start+2, .... end-1 are >= n. And so on
public static int count(int[] A, int n) {
int start = 0;
int end = A.length - 1;
int count = 0;
while (start < end) {
int sum = A[start] + A[end];
if (sum < n) {
start++;
} else {
count += end - start;
end--;
}
}
return count;
}
O(log n) solution:
class Program
{
private static int targetIndex = 9;
static void Main(string[] args)
{
// Time complexity is O(log n)
int sum = 0;
int[] test = {1,2,3,4,5,6,7,8,9,10};
for (int i = 0; i < test.Length - 1; i++ )
{
var temp = 0;
GetTargetIndexForEachElement(test, i, 0, targetIndex, 7);
if(targetIndex <= i)
{
temp = test.Length - i - 1;
}
else
{
temp = test.Length - targetIndex;
}
sum += temp;
}
Console.WriteLine(sum);
}
private static void GetTargetIndexForEachElement(int[] array, int current, int start, int end, int limit)
{
// Brute force.
if(start+1 >= end)
{
for(int i=start; i<=end; i++)
{
if(array[current] + array[i] > limit)
{
targetIndex = i;
break;
}
}
}
else
{
int midIndex = (start + end)/2;
// Recursion modify value of a private static integer to make it work.
if (array[current] + array[midIndex] < limit)
GetTargetIndexForEachElement(array, current, midIndex, end, limit);
else if (array[current] + array[midIndex] > limit)
GetTargetIndexForEachElement(array, current, start, midIndex, limit);
else
{
targetIndex = midIndex + 1;
}
}
}
}
public int findCountOf2NumbersGreaterThanN(int[] sortedArray, int n) {
int countOfSumOfTwoNumbers = 0;
int frontPositionPointer = 0;
int countOfPreviousNumber = 0;
int backPositionPointer = sortedArray.length -1;
while(frontPositionPointer != backPositionPointer) {
int sum = sortedArray[frontPositionPointer] + sortedArray[backPositionPointer];
if (sum > n) {
countOfPreviousNumber++;
backPositionPointer--;
} else {
countOfSumOfTwoNumbers += countOfPreviousNumber;
frontPositionPointer++;
}
}
if (frontPositionPointer == backPositionPointer) {
countOfSumOfTwoNumbers += countOfPreviousNumber;
frontPositionPointer++;
}
for (int i = frontPositionPointer ; i< sortedArray.length; i++) {
countOfSumOfTwoNumbers += (sortedArray.length) - (i +1);
}
return countOfSumOfTwoNumbers;
}
public int findCountOf2NumbersGreaterThanN(int[] sortedArray, int n) {
int countOfSumOfTwoNumbers = 0;
int frontPositionPointer = 0;
int countOfPreviousNumber = 0;
int backPositionPointer = sortedArray.length -1;
while(frontPositionPointer != backPositionPointer) {
int sum = sortedArray[frontPositionPointer] + sortedArray[backPositionPointer];
if (sum > n) {
countOfPreviousNumber++;
backPositionPointer--;
} else {
countOfSumOfTwoNumbers += countOfPreviousNumber;
frontPositionPointer++;
}
}
if (frontPositionPointer == backPositionPointer) {
countOfSumOfTwoNumbers += countOfPreviousNumber;
frontPositionPointer++;
}
for (int i = frontPositionPointer ; i< sortedArray.length; i++) {
countOfSumOfTwoNumbers += (sortedArray.length) - (i +1);
}
return countOfSumOfTwoNumbers;
}
public class HelloWorld{
public static void main(String []args){
int a[] = { 1, 5, 7, 9, 30, 33, 35, 65, 67 };
System.out.println(getCount(a, 100));
}
public static int getCount(int[] arr, int n){
int count=0; int j=0;
int i=arr.length-1;
for( ;i>=0; ){
if(i>j){
if(arr[i]+arr[j]>=n){
count+= i-j;
i--;
} else{
j++;
}
} else{
break;
}
}
return count;
}
}
//SUM Provided as input
static int SUM = 5;
public static void main(String[] args)
{
Integer a[] = new Integer[]{0, 1, 2, 3, 4, 6};
int count = getCountSum(a, 0, a.length-1);
System.out.println("Count = "+ count);
}
private static int getCountSum(Integer a[],int start ,int end)
{
if (start >= end)
return 0;
if ((a[start] + a[end]) > SUM)
return (end - start ) + getCountSum(a, start , end-1 );
else if ((a[start] + a[end]) < SUM)
return getCountSum(a, start + 1, end);
else
return (end - start ) + getCountSum(a, start + 1, end-1 );
}
Simple Solution:
int main() {
/*Given a sorted array and n, find the count of sum of 2 numbers greater than or equal to n*/
int chr[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int n = 10;
int arrSize = sizeof(chr) / sizeof(*chr);
int count = 0;
for (int i = 0; i < arrSize; i++)
{
for (int j = 0; j < arrSize; j++)
{
if (((chr[i] + chr[j]) >= n) && (i != j))
count++;
}
}
cout << count;
}
O(n) solution
- Omri.Bashari June 17, 2015int count_pairs_ge(int* a, const int size, const int n) { auto si = 0; auto ei = size - 1; auto count = 0; while (si < ei) { if (a[si] + a[ei] >= n) { count += ei - si; --ei; } else { ++si; } } return count; } void test_count_pairs_ge() { int a[] = { 1, 5, 7, 9, 30, 33, 35, 65, 67 }; assert(21 == count_pairs_ge(a, sizeof(a) / sizeof(int), 42)); assert(1 == count_pairs_ge(a, sizeof(a) / sizeof(int), 120)); assert(32 == count_pairs_ge(a, sizeof(a) / sizeof(int), 13)); assert(0 == count_pairs_ge(a, sizeof(a) / sizeof(int), 150)); }