Determining whether or not a binary array has two consecutive 1s with less than n index accesses?
Say we have an array of size n, with each index containing the values 0 or 1. We need to determine whether or not the array contains two consecutive 1 bits.
For which values of n in the range {3, 4, 5, 6, 7} can this be done by checking fewer than n elements (in the worst case)?
My attempt:
When n is in {4,7}, we can determine if there are consecutive 1's without checking all the elements.
For 4, we can do this by checking the either of the middle two elements. If either of them is 0, then we no longer have to check the index on its outer side.
For we first check if the 2nd index has a 1, if it does then we check the 1st and 3rd element. If there is not a consecutive pair, then we move on to the 6th element. If it has a 1, then we check the 5th and 7th element. If there is no consecutive pair, then we return false. However, if the 6th element did not contain a 1, then we consider the 4th and 5th element. This is a max total of 6 indexes checks for any list combination of 1's and 0's of size 7.
Am I missing something? I sort of just tried out random algorithms to see if I can get less than n index accesses for each value of n. How can I prove that {3,5,6} can't be done with less than n index checks?
See also questions close to this topic

Get the existing intersections between multiple object arrays
I have a couple of arrays which have some same ids. What I want to achieve is get the intersections between the arrays in plain javascript, no libraries. If there is a match of Ids and arraypicklist values are not equal between 2 or more arrays I should get an array with the matching Ids.
Below is my example which I tried but this ends up with no ids where I expect at least 1 match. In this case Id:123 as in the first and second array there is a match. So I would expect
intersection = [{"Id":"123","arrayPicklist":"Categorie__c"},{"Id":"123","arrayPicklist":"Regio__c"}];
fiddle:https://jsfiddle.net/ozckc0tw/4/
var buckets = [[{"Id":"123","arrayPicklist":"Categorie__c"}], [{"Id":"123","arrayPicklist":"Regio__c"}], [{"Id":"124","arrayPicklist":"Categorie__c"}], [{"Id":"123","arrayPicklist":"Regio__c"},{"Id":"125","arrayPicklist":"Regio__c"},{"Id":"123","arrayPicklist": "Regio__c"},{"Id":"126","arrayPicklist":"Regio__c"}]] function IntersectionByKey(key) { var i, j, k, ret = [], item, args = [].slice.call(arguments, 1); args.sort(function(a, b) {return a.length  b.length}); i:for(i=0; i<args[0].length; i++) { item = [Object.assign(args[0][i], {})]; j:for(j=1; j<args.length; j++) { for(k=0; k<args[j].length; k++) { if(key in args[0][i] && args[0][i][key] == args[j][k][key]){ item.push(Object.assign(args[j][k], {})); continue j; } } continue i; } ret.push(item); } return ret; } var key = 'Id'; var intersection = IntersectionByKey.apply(null, [key].concat(buckets)); console.log('intersection '+JSON.stringify(intersection))

load array from TextView in android studio
Is it possible to get array value from a
TextView
? In my android project I need to get value of array string from a TextViewfinal String[] amountArray = {"100$","575$","50$","70$","60$"} (TextView) textView = (TextView) findViewById(R.id.textView);
This above code I write currently. I can't understand what to do now?
I want like below
amountArray = textView.getText().toString();
but I know it will not work, because the value of TextView is String, and
amountArray
is a array string.So, how can i convert the value of TextView to a array string and asign it to amountArray.
*The value of TextView is also:
{"100$","575$","50$","70$","60$"}

android how to get the common string by comparing three array list of string type?
Android i have three array list of string type i need to find the common string appearing in these three array list .how to get the common string from three Arraylist of string type?

Optimize bruteforce solution of searching nearest point
I have non empty Set of points scattered on plane, they are given by their coordinates. Problem is to quickly reply such queries:
Give me the point from your set which is nearest to the point A(x, y)
My current solution pseudocode
query( given_point ) { nearest_point = any point from Set for each point in Set if dist(point, query_point) < dist(nearest_point, given_point) nearest_point = point return nearest_point }
But this algorithm is very slow with complexity is
O(N)
.The question is, is there any data structure or tricky algorithms with precalculations which will dramatically reduce time complexity? I need at least
O(log N)
Update
By distance I mean Euclidean distance

Fewer line to count max int in array on Kotlin and faster than O(nlogn)?
I wonder if there a better way or idiomatic way to count the max int in an array with Kotlin and faster than O(nlogn)?
This code gives O(n) but I feel like it too long
fun countMax(n: Int, ar: Array<Int>): Int { val max = ar.max(); var countMax = 0 for(i in ar) if(i==max) countMax++ return countMax } fun main(args: Array<String>) { val scan = Scanner(System.`in`) val n = scan.nextLine().trim().toInt() val ar = scan.nextLine().split(" ").map{ it.trim().toInt() }.toTypedArray() val result = birthdayCakeCandles(n, ar) println(result) }
Sorting then counting got nlogn
val input: Scanner = if (inputFile.exists()) Scanner(inputFile) else Scanner(System.
in
)fun main(args: Array<String>) { input.nextLine() val nums = input.nextLine().split(' ').map { it.toLong() }.sorted() val s = nums.takeLastWhile { it == nums.last() }.size print(s) }
I wonder there is a shorter code and perform faster than O(nlogn)

Unable to allocate memory for a new node in my c implementation of graph
I'm implementing a graph in C, here is my program:
#include <stdio.h> #include <ctype.h> #include <stdlib.h> #include <string.h> #include <limits.h> typedef struct EdgeNode{ int adjvex; struct EdgeNode *nextarc; }ENode, *PENode; typedef struct VertexNode{ char *data; ENode *firstarc; }VNode; typedef struct MyGraph{ VNode vertices[INT_MAX]; }Graph; static int get_pos(Graph g, char* name, int num_ver){ int i; for (i = 0; i < num_ver; i++){ if(strcmp(g.vertices[i].data,name) == 0) return i; } return 1; } void add_node(ENode *mylist, ENode *newEdge){ ENode *p = mylist; while(p>nextarc) p = p>nextarc; p>nextarc = newEdge; } void DFS(Graph G, int first_node, int* visited){ ENode *new_edge; visited[first_node] = 1; new_edge = G.vertices[first_node].firstarc; while (new_edge != NULL){ if (!visited[new_edge>adjvex]) DFS(G, new_edge>adjvex, visited); new_edge = new_edge > nextarc; } } static int dfs_traverse(Graph G, int first_node, int second_node, int number_of_nodes){ int visited[INT_MAX]; int i; for (i = 0; i < number_of_nodes; i++){ visited[i] = 0; } DFS(G, first_node, visited); if (visited[second_node] == 1){ return 1; }else{ return 0; } } void print_graph(Graph G, int num_vertex) { int i; ENode *node; printf("List Graph:\n"); for (i = 0; i < num_vertex; i++) { printf("%d(%s): ", i, G.vertices[i].data); node = G.vertices[i].firstarc; while (node != NULL) { printf("%d(%s) ", node>adjvex, G.vertices[node>adjvex].data); node = node>nextarc; } printf("\n"); } } int main (){ size_t sz1; char *line = NULL; //char line[1024]; char make_nodes[] = "@n"; char make_edges[] = "@e"; char check_edges[] = "@q"; static int i = 0; int index_1, index_2; int dfs_1, dfs_2; int pathExists; ENode* Edge1; Graph* pGraph = malloc(sizeof(Graph)); if (pGraph == NULL){ fprintf(stderr, "Unable to allocate memory for new node\n"); exit(1); } while(getline(&line, &sz1, stdin) > 0){ char cmd[3],n1[65],n2[65],dummy[2]; int num_args; num_args = sscanf(line,"%3s%64s%64s%2s",cmd,n1,n2,dummy); if (strcmp(cmd,make_nodes) == 0){ if(num_args != 2){ printf("error\n"); }else{ pGraph>vertices[i].data = strdup(n1); pGraph>vertices[i].firstarc = NULL; i++; printf("the node is %s\n",pGraph>vertices[i].data); } }if (strcmp(cmd,make_edges) == 0){ if (num_args != 3){ printf("error\n"); }else{ index_1 = get_pos(*pGraph, n1, i); index_2 = get_pos(*pGraph, n2, i); Edge1 = (ENode*)malloc(sizeof(ENode)); Edge1 > adjvex = index_2; if (pGraph > vertices[index_1].firstarc == NULL) pGraph > vertices[index_1].firstarc = Edge1; else{ add_node(pGraph>vertices[index_1].firstarc, Edge1); } } } } print_graph(*pGraph,i); return 0; }
While the program should be working as follows:
@n [somenode] for adding a new node @e [somenode] [somenode] for adding a new edge @q [somenode] [somenode] for testing the connection between two nodes
Which should be like:
@n first @n second @e first second @q first second 1 //which means first and second is connected
However, given all those information, my program crash, when I use valgrind, it simply returns the message:
==7758== Memcheck, a memory error detector ==7758== Copyright (C) 20022013, and GNU GPL'd, by Julian Seward et al. ==7758== Using Valgrind3.10.1 and LibVEX; rerun with h for copyright info ==7758== Command: ./reach ==7758== Unable to allocate memory for new node ==7758== ==7758== HEAP SUMMARY: ==7758== in use at exit: 0 bytes in 0 blocks ==7758== total heap usage: 0 allocs, 0 frees, 0 bytes allocated ==7758== ==7758== All heap blocks were freed  no leaks are possible ==7758== ==7758== For counts of detected and suppressed errors, rerun with: v ==7758== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
If I just test by reading from stdin, it works like that:
@n first the node is (null) @n second the node is (null) @e first second Segmentation fault (core dumped) @q first second Segmentation fault (core dumped)
I don't know if there's sufficient information for that, but anyone has ideas what may have happended?