arrays,sorting,find,sum , Finding a number that is sum of two other numbers in a sorted array

## Question:

Tag: arrays,sorting,find,sum

As it said in the topic, I have to check if there is a number that is the sum of two other numbers in a sorted array.

In first part of the question (for a unsorted array) I wrote a solution, just doing 3 loops and checking all the combinations.

Now, I can't understand how to build the most efficient algorithm to do the same, but with a sorted array.

Numbers are of type `int` (negative or positive) and any number can appear more then once.

Can somebody give a clue about that logic problem ?

Here I am doing it using C:

An array A[] of n numbers and another number x, determines whether or not there exist two elements in S whose sum is exactly x.

METHOD 1 (Use Sorting)

Algorithm:

hasArrayTwoCandidates (A[], ar_size, sum) 1) Sort the array in non-decreasing order.

2) Initialize two index variables to find the candidate elements in the sorted array.

(a) Initialize first to the leftmost index: l = 0

(b) Initialize second the rightmost index: r = ar_size-1

3) Loop while l < r.

(a) If (A[l] + A[r] == sum) then return 1

(b) Else if( A[l] + A[r] < sum ) then l++

(c) Else r--

4) No candidates in whole array - return 0

Example: Let Array be {1, 4, 45, 6, 10, -8} and sum to find be 16

Sort the array A = {-8, 1, 4, 6, 10, 45}

Initialize l = 0, r = 5

A[l] + A[r] ( -8 + 45) > 16 => decrement r. Now r = 10

A[l] + A[r] ( -8 + 10) < 2 => increment l. Now l = 1

A[l] + A[r] ( 1 + 10) < 16 => increment l. Now l = 2

A[l] + A[r] ( 4 + 10) < 14 => increment l. Now l = 3

A[l] + A[r] ( 6 + 10) == 16 => Found candidates (return 1)

Implementation:

``````# include <stdio.h>
# define bool int

void quickSort(int *, int, int);

bool hasArrayTwoCandidates(int A[], int arr_size, int sum)
{
int l, r;

/* Sort the elements */
quickSort(A, 0, arr_size-1);

/* Now look for the two candidates in the sorted
array*/
l = 0;
r = arr_size-1;
while(l < r)
{
if(A[l] + A[r] == sum)
return 1;
else if(A[l] + A[r] < sum)
l++;
else // A[i] + A[j] > sum
r--;
}
return 0;
}

/* Driver program to test above function */
int main()
{
int A[] = {1, 4, 45, 6, 10, -8};
int n = 16;
int arr_size = 6;

if( hasArrayTwoCandidates(A, arr_size, n))
printf("Array has two elements with sum 16");
else
printf("Array doesn't have two elements with sum 16 ");

getchar();
return 0;
}

/* FOLLOWING FUNCTIONS ARE ONLY FOR SORTING
PURPOSE */
void exchange(int *a, int *b)
{
int temp;
temp = *a;
*a   = *b;
*b   = temp;
}

int partition(int A[], int si, int ei)
{
int x = A[ei];
int i = (si - 1);
int j;

for (j = si; j <= ei - 1; j++)
{
if(A[j] <= x)
{
i++;
exchange(&A[i], &A[j]);
}
}
exchange (&A[i + 1], &A[ei]);
return (i + 1);
}

/* Implementation of Quick Sort
A[] --> Array to be sorted
si  --> Starting index
ei  --> Ending index
*/
void quickSort(int A[], int si, int ei)
{
int pi;    /* Partitioning index */
if(si < ei)
{
pi = partition(A, si, ei);
quickSort(A, si, pi - 1);
quickSort(A, pi + 1, ei);
}
}
``````

# Related:

## Passing an array through a constructor

java,arrays,constructor
This is what I have so far: import java.util.*; public class SArray { private int[] array; public SArray(int a[]) { this.array = a; } public String toString() { String arrayString = ""; int i = 0; while (i < array.length) { arrayString = arrayString + array[i]; i++; } return arrayString;...

## Zipping two arrays together with index in Scala?

arrays,scala,zip
I have two arrays populated with integers. They are the same size (val array1 and val array2). I want to fuse them together into tuples with their index as the third element. For example if we have val array1 = Array(5,2,6,2) and val array2 = Array(9,8,3,4) then I want to...

## Translating a character array into a integer string in C++

c++,arrays,string
I was trying to achieve translating a character array into a integer string and corresponding character to their alphabetical order. For instance: A(a) = 0 , Z(z) = 25. string key_char = argv[1]; string key_num; for (int i = 0; i < key_char.length(); i++){ if (isalpha(key_char[i])){ if (islower(key_char[i])){ key_num[i] =...

## Split an array into slices, with groupings

arrays,ruby,enumerable
I've got some Ruby code here, that works, but I'm certain I'm not doing it as efficiently as I can. I have an Array of Objects, along this line: [ { name: "foo1", location: "new york" }, { name: "foo2", location: "new york" }, { name: "foo3", location: "new york"...

## Having two arrays in variable php

php,mysql,arrays,variables,multidimensional-array
i've this code, i'm trying to explode my date e.g "04 June 2015" to have the day and the month in other 2 variables, but i have all in a method, with an array, is it possible, my code doesn't work, it writes "Array[0]" why? while (\$i < \$number) {...

## char* string substract function throws exception

c++,arrays,string,char
I'm working on my own string class called PString, I have this function that finds a specific character, like 6, and now I have this function called substr short fo substract, where I want to substract from 0 to [insertnumber]. the way I'm trying to call this is by doing...

## most efficient way to create javascript array out of various php arrays

javascript,php,jquery,arrays
I have a form that a user can submit multiple times, adding different information each time. These form inputs are translated into php \$_SESSION arrays, so each time the user hits the submit button, the array grows. This is working fine. I need to bring these over into javascript but...

## is there an equivalent of the ruby any method in javascript?

javascript,arrays,ruby,iteration
Is there an equivalent of ruby's any method for arrays but in javascript? I'm looking for something like this: arr = ['foo','bar','fizz', 'buzz'] arr.any? { |w| w.include? 'z' } #=> true I can get a similar effect with javascript's forEach method but it requires iterating through the entire array rather...

## do calculation inside JSONArray in Java

java,arrays,json
I have a simple issue but cannot solve it as I am not very good at algorithm! I have an JSONArray in this form: [{"values":[{"time":1434976493,"value":"50"}, {"time":1434976494,"value":"100"}],"counter":"counter1"}, {"values":[{"time":1434976493,"value":"200"}, {"time":1434976494,"value":"300"}],"counter":"counter2"}, {"values":[{"time":1434976493,"value":"400"}, {"time":1434976494,"value":"600"}],"counter":"total"}] What I want to do is to get the integer value for counter 1 and counter 2 and then divide...

## Substring of a file

javascript,arrays,substring
I have a file that is structure like this : var file = "a|b|c|d, a|b|c|d, a|b|c|d, a|b|c|d, a|b|c|d"; Now I would extract all letters "c" and "d" of this file and put those letter in array, structure like this: var array = [ [a,b,1], [a,b,2], [a,b,3], [a,b,4], [a,b,5] ]; How...

## textbox search through array with keys and display closest results

javascript,jquery,arrays
So, I'm not sure if there is a better method of what I'm trying to do, but effectively I have an array of about 12,000 elements, and each has a key in the format of: var arrayObj = { "blue": 'key1', "orange": 'key2', "red": 'key3', "black": 'key4', //ect... } I...

## SCALA: change the separator in Array

arrays,string,scala,delimiter
I have an Array like this. scala> var x=Array("a","x,y","b") x: Array[String] = Array(a, x,y, b) How do I change the separator comma in array to a :. And finally convert it to string like this. String = "a:x,y:b" My aim is to change the comma(separators only) to other separator(say,:), so...

## pointer to pointer dynamic array in C++

c++,arrays,pointers
I've been having bad luck with dynamic pointers when I want to close it. why the application wrote to memory after end of heap buffer? how can I close my array? int main() { . . int **W; W = new int* [n]; for (int i=1; i <= n; i++)...

## Javascript sort array of objects in reverse chronological order

javascript,arrays,sorting
I have an array of objects which holds a list of jobs and I would like to sort them in reverse chronological order as they would appear on a resume for example. I came up with the below solution which 'seems' to work but I was wondering if there is...

## How to check if data already exists then randomly generate new data from an Array

php,mysql,arrays,mysqli
Okay so, I made an array containing 270+ different strings. The main goal is too echo out 60 strings from that array and combine them.. Ex. 1.String, 1.String2. The 2 echo'd out strings are a combination, and should be together like 1-1 and 2-2, 3-3, and ect. In total there...

## Perl: Using Text::CSV to print AoH

arrays,perl,csv
I have an array of hashes (AoH) which looks like this: \$VAR1 = [ { 'Unit' => 'M', 'Size' => '321', 'User' => 'test' } { 'Unit' => 'M' 'Size' => '0.24' 'User' => 'test1' } ... ]; How do I write my AoH to a CSV file with separators,...

## Sorting vector of Pointers of Custom Class

c++,sorting,c++11,vector
I have vector<FPGA*> current_generation_, which I'd like to sort by FPGA member fitness_ using the sort_members function. Applicable code follows: bool sort_members (FPGA* fpga_first, FPGA* fpga_second) { return (fpga_first->fitness() < fpga_second->fitness()); }; fpga.hpp #include <vector> class FPGA { public: explicit FPGA(int input_gates, int output_gates, int normal_gates); const int fitness(); protected:...

## php for loop of an array

php,html,arrays,for-loop
I have an html form that passes an array into php and then does a for loop to print out values. This is the code that I have \$payloads = \$_POST['topay']; \$loadNum = \$_POST['loadnum']; \$unit = \$_POST['unit']; \$driver = \$_POST['driver']; for(\$i=0;\$i<count(\$payloads);\$i++) { echo \$payloads[\$i]; echo "<br>"; echo '<td width="50" valign="top">'.\$loadNum[\$i].'</td>';...

## Array JLabel ActionListener multiple JPanels

java,arrays,swing
I have an array of JLabels and I want to add an ActionListener to them. Every label should display a panel and the other should be removed. How can I realize this?

## Create array from another with specific indices

javascript,arrays
I have two arrays, one of data and one of indices: var data = [ 'h', 'e', 'l', 'l', 'o', ' ' ]; var indices = [ 4, 0, 5, 0, 1, 2, 2 ]; I would like to create a third array, using cells of data in order indicated...

## Notice: Array to string conversion in “path of php file” on line 64

php,mysql,arrays,oracle
PHP CODE -: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <title>Untitled Document</title> </head> <body> <?php \$rows =0; \$fp = fopen("leave1.csv","r"); if(\$fp){ while(!feof(\$fp)){ \$content = fgets(\$fp); if(\$content) \$rows++; } } fclose(\$fp); //echo \$rows; \$_SESSION['rows'] = \$rows; ?>...

## How to pivot array into another array in Ruby

arrays,ruby,csv
I have a multidimensional array like this one : myArray = [["Alaska","Rain","3"],["Alaska","Snow","4"],["Alabama","Snow","2"],["Alabama","Hail","1"]] I would like to end up with CSV output like this. State,Snow,Rain,Hail Alaska,4,3,nil Alabama,2,nil,1 I know that to get this outputted to CSV the way I want it I have to have output array like this: outputArray =[["State","Snow","Rain","Hail"],["Alaska",4,3,nil],["Alabama",2,nil,1]]...

## C++ & Qt: Random string from an array area

c++,arrays,string,qt,random
In my small Qt application, I want to pick a random string out of an array after I clicked on a button. I've read many threads but nothing works for me. So in my slot there's an array with several strings in it. I also implemented <string>, <time.h> and srand....

## Javascript: Labeling array results

javascript,arrays
Alright so here is my Html code: <html> <head> <title>Planning</title> <script type="text/javascript" src="Function.js"></script> </head> <body> <form id="form"> <h1><b>Please enter data</b></h1> <hr size="3"/> <br> <label for="Name">Name:</label> <input id="Name" type="text" /> <br> <label for="Date">Date: </label><input id="Date" type="text" /> <br> <label for="Plans">Plans:...

## Java, cut off array line before charactern nr. X

java,arrays,string,break
So i have massive(i mean massive) array. It has over 500000 lines. Each line starts with some bs that i don't need. What i need is EVERYTHING after 64th symbol(65th symbol is needed). It's the same for every line, but after 64th symbol each line lenght is different. How do...

## Sort when values are None or empty strings python

python,list,sorting,null
I have a list with dictionaries in which I sort them on different values. I'm doing it with these lines of code: def orderBy(self, col, dir, objlist): if dir == 'asc': sorted_objects = sorted(objlist, key=lambda k: k[col]) else: sorted_objects = sorted(objlist, key=lambda k: k[col], reverse=True) return sorted_objects Now the problem...

## how to modify an array value with given index?

arrays,linux,bash
I want to modify an array cell, which I can do when I know the cell as a number. However here my cell position is given by \$i. pomme[`\${i}`]="" I tried without the `` and it doesn't work either? How am I suppose to do it?...

## Merging array values into single key and multiple values in php

php,arrays
I want the array to merge into a key value pair. look at the example below Here is my code and array \$aExtraFilter array (size=4) 0 => array (size=2) 'key' => string 'CookTech' (length=8) 'value' => string 'Broil' (length=5) 1 => array (size=2) 'key' => string 'CookTech' (length=8) 'value' =>...

## array and function php

php,arrays
I'm just a beginner in PHP coding. I've been reading through a tutorial, but having some trouble with basic PHP concepts. If you could help me, I'd be much obliged. I'm having trouble understanding why the following code doesn't work. <?php function sum(\$x, \$y) { \$z = \$x + \$y;...

## Javascript function to validate contents of an array

javascript,arrays
Here's what is asked: validItems(items) – this function receives a string array of items which are to be for a customer. The function returns an empty string indicating all item codes in the array are valid; otherwise the function returns the first invalid item code in the array. All item...

## Select word between two words

javascript,arrays,jquery-selectors
How can I create a function that selects everything between the words X and Y and pushes it to an array. By Greili - 4 Hours and 40 Minutes ago. #NsShinyGiveaway 0 comments By ToneBob - 4 Hours and 49 Minutes ago. #NsShinyGiveaway 0 comments By hela222 - 5 Hours...

## Get elements containing text from array

javascript,jquery,html,arrays,contains
I want to search all the elements containing any string in the array. For example I have following list of items <ul> <li>cricket bat</li> <li>tennis ball</li> <li>golf ball</li> <li>hockey stick</li> </ul> and this array var arr = ['bat', 'ball']; It should select all the elements having text bat and ball....

## Merge and sum values and put them in an array

javascript,arrays,angularjs,foreach
I'm retrieving values from an external source and apply a foreach loop to the results, with the code below. angular.forEach(data, function(value, key) { if (value.start_date > firstdayOfWeek && value.start_date < lastdayOfWeek) { console.log(value.firstname + ' - ' + value.distance); } else { //do nothing } }); The result is console...

## How to innerHTML a function with array as parameter?

javascript,arrays,loops,foreach,innerhtml
I am learning about looping thorugh arrays - I want to pass the result of an if else statement in the forEach function (inside another function with array as parameter) to HTML using innerHTML (does not have to be innerHTML if you know better methods I do not mind). It...

## WPF Listbox Collection custom sort

wpf,sorting,listbox,compare,collectionview
I have a listbox DropPrice MyPrice Price1 Price2 I want to sort it like this Price1 Price2 DropPrice MyPrice I mean, if there's an item that starts with the sequence "price", it gets priority, else the smallest string should get the priority. My source code: var lcv = (ListCollectionView)(CollectionViewSource.GetDefaultView(_itemsSource)); var...

## Given an array/object of datetimes, how can I return an array/object of the times sorted by hour and times sorted by days of the week

php,arrays,sorting,datetime,laravel
PHP/Laravel, I'm getting an array of objects that includes date times for each record. I need to generate analytics on objects on an hourly basis of a day and daily basis of a week. So for example: For a date range of 1/1/2015 - 1/10/2015 I return 100 records all...

## Ruby: How to copy the multidimensional array in new array?

ruby-on-rails,arrays,ruby,multidimensional-array
seating_arrangement [ [:first, :second, :none], [:first, :none, :second], [:second, :second, :first], ] I need to copy this array into new array. I tried to do it by following code: class Simulator @@current_state def initialize(seating_arrangement) @@current_state = seating_arrangement.dup end But whenever I am making any changes to seating_arrangement current_state changes automatically....

## accessing range of values in arduino array

arrays,arduino
I have data packet coming in like this in Arduino. Data: 12345678901234 I can access the 5th value using the code below. id = sx1272.packet_received.data[4]; My question is how do I access a rang of values? I tried this, but the colon throws an error. char[2] id; if( sx1272.packet_received.length >...

## jQuery - Value in Function

jquery,arrays,function
My array: array.name = "Thiago"; array.date = "01/01/1990"; I want a function like this: function myFunc( array, fieldToCompare, valueToCompare ) { if( array.fieldToCompare == "Thiago" ) alert(true); } myFunc( myArray, name, "Thiago" ); is it possible?...

## Blank screen on GridView

android,arrays,gridview
I'm trying to create a GridView with an array of strings. These are XML, and MainActivity and Adapter, but what I get is a blank screen. I'm change the background, but the result is the same, but clicking on a point on the screen appears to me the toast stating...

## How to pass array in rails 4 strong parameters

ruby-on-rails,arrays
I have to pass a array of food_item_ids in my order_controller. Every order will have many food_items. How can I pass these food_items_id as an array in strong parameters. orders_controller.rb def create @order = Order.new(order_params) if @order.save render :json, @order, status:201, location: [:api, @order] else render :json, { errors: @order.errors...

## How do I print more than one value per key in Tcl?

arrays,tcl
array set array_in_twos { set1 table set2 chair set1 chair } foreach combo [array names array_in_twos] { puts "\$combo is \$array_in_twos(\$combo)," } outputs: set1 is chair, set2 is chair, It seems the second 'set 1' replaces the first 'set 1'. how do i print all? set1 is table, set2 is...

## Comparing arrays with numbers in vb.net

arrays,vb.net
I need a way to compare two arrays in vb.net and save result in third array: Dim KonRes(3) As Integer Dim UserRes(3) As Integer Dim YelRed(3) As Integer KonRes(0) = 1 KonRes(1) = 2 KonRes(2) = 3 KonRes(3) = 4 UserRes(0) = 4 UserRes(1) = 3 UserRes(2) = 2 UserRes(3)...

## Javascript Sorting Array of Objects [duplicate]

javascript,arrays,sorting,object
This question already has an answer here: Sorting an array of JavaScript objects 14 answers (Please excuse any errors - this is my first post and I am also relatively new to Javascript) I'm trying to sort an array of objects by a specific property value in Javascript. I...

## Segmentation Fault if I don't say int i=0

c,arrays,segmentation-fault,initialization,int
void removeVowels(char* array){ int i,j,v; i=0; char vowel[]={'a','e','i','o','u'}; while(array[i]!='\0') { for(v=0;v<5;v++) { if (array[i]==vowel[v]) { j=i; while(array[j]!='\0') { array[j]=array[j+1]; j++; } i--; break; } } i++; } } in function removeVowels() if I don't include i=0; and just say int i; why does it give segmentation fault? Isn't it automatically...