Country: United States

Comment hidden because of low score. Click to expand.
16
of 16 vote

O(n) solution

``````int 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));
}``````

Comment hidden because of low score. Click to expand.
0

This is the solution I gave and interviewer was expecting the same, although needed a small hint.

Comment hidden because of low score. Click to expand.
1
of 1 vote

why it's O(n)? looks like O(array_size) which could be larger or less than O(n).

Comment hidden because of low score. Click to expand.
0

``````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;
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

Nice solution, but it doesn't seem to me a O(n) solution when I try to calculate a "loose" upper bound complexity. Can somebody prove it pls?

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

Comment hidden because of low score. Click to expand.
0

No, it's 2 different numbers in the array

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

nLogn solution -> for every integer lookup position of sum - arr and add n-that position to count. Do this iteratively till second last element.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0

Beautiful

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int findCountOfSumGreaterThanN(int[] a, int n){
int front = 0, end = a.length - 1;

if (a.length <= 1) return 0;

int count = 0;
while(front < end){
int fval = a[front];
int eval = a[end];

if (fval + eval > n) {
count++;
end--;
}

if (fval + eval <= n) front++;
}

return count;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

int twoSum(vector<int> &nums, int target) {
int ans = 0;
for (int i=0; i<nums.size(); i++) {
int index = lower_bound(nums.begin()+i+1, nums.end(), target-nums[i])-nums.begin();
ans += nums.size()-index+1;
}
return ans;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//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 );
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it should be as simple as adding up last two numbers of array as array is sorted. If it is greater than N then return it otherwise no such element is found.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.