Is “Solving two-variable quadratic polynomials over the Integers” is an NP-Complete Problem?

On this Wikipedia article, it claims that given $ A, B, C \geq 0, \; \in \mathbb{Z}$ , finding $ x, \,y \geq 0, \, \in \mathbb{Z}$ for $ Ax^2+Bx^2-C=0$ is NP-complete? Given by how easy I can solve some (with nothing but Wolfram), it doesn’t seem right. I’m sure it’s either written incorrectly or I’m just misunderstanding something.

Is there a way to determine whether a list of integers can be a prefix function?

Say you had

(0,0,0,1,2,3,4,5,6,7,8,9,10)

or

(0,1,0,1,0,1,2,3,0,1,0,0,1)

Could you use, for example, the KMP algorithm to deduce the validity of the above lists as prefix functions? I know there is a way to find whether a substring exists in a string using KMP, but is there a way to do it the other way around, starting at the apparent prefix function and ascertaining that it is indeed a possible prefix function, without knowing the string/substring itself at the start?

Checking equality of integers: O(1) in C but O(log n) in Python 3?

Consider these equivalent functions in C and Python 3. Most devs would immediately claim both are O(1).

def is_equal(a: int, b: int) -> bool:   return a == b 
int is_equal(int a, int b) {   return a == b } 

But consider what is happening under the surface. Integers are just binary strings and, to determine equality, both languages will compare the strings bit-by-bit. In either case this scan is O(b) where b is the number of bits. Since integers have a constant size in bits in C, this is simply O(1).

In Python 3 however, integers do not have fixed size and the scan remains O(b) for the number of bits in the input, or O(log a) where a is the value of the input in base 10.

So if you’re analyzing code in Python, any time you compare two integers, you are embarking on a surprisingly complex journey of O(log n) with respect to the base 10 value of either number.

For me this raises several questions:

  1. Is this correct? I haven’t seen anyone else claim that Python compares ints in log time.
  2. In the context of conducting an interview, should you notice or care if a candidate calls this O(1)?
  3. Should you notice or care about this distinction in the real world?

Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets


Question: Given a list of integers (possibly negative) and a target integer, return the number of triplets whose product is the target integer and two of the triplets must be adjacent.

More precisely, given a triplet $ (i,j,k)$ with $ i<j<k,$ it satisfies the question above if $ A[i] \times A[j] \times A[k] = target$ and either ($ j = i+1$ and $ k > j+1$ ) or ($ k = j+1$ and $ i < j -1$ .)

For example, if the list given is $ A = [1,2,2,2,4]$ and target $ = 8,$ then the answer is $ 3$ as $ (0, 1, 4) , (1, 2, 3)$ and $ (0, 3, 4)$ are the only triplets satisfying conditions above if we use $ 0$ -based numbering.

I stucked at this question for 3 hours and not able to solve it.

Any hint is appreciated.

Predict the next base64 code in an enumnation attack on sequntial integers that have been turned to base64 code

1tL1K/nYW1Q= corresponds to 41154

sR4 ngjRepM= corresponds to 41155

“hint the above code does have a space”

the above codes are base64 and correspond to some string + orderids

I am doing this in .NET

If someone able to crack the series as I am trying to create this in custom code.

I want someone to test this and try to break it, so that I can see the flaw in my code.

The point is that I use the int codes in .Net with a preset string to generate the base64 codes. I am using this to prevent order enumeration attacks, yet have a small identifier instead of ints for order numbers. Do you think this is susceptible to attacks and whether you can work out what the “secret” is to producing the base64 codes to recognise orders, and enumerate them based on existing data I have provided.

I will place a bounty of 100 credits on this if someone can crack this.

Thanks

Finding the smallest number that scales a set of irrational numbers to integers

Say we have a set $ S$ of $ n$ irrational numbers $ \left\{a_1, …, a_n\right\}$ .

Are there any known algorithms that can determine a scaling factor $ s \in \mathcal{R}$ such that $ s * a_i \in \mathcal{N} \;\forall a_i \in S$ , assuming that such factor exists? If multiple exist, how about the smallest one?

Moreover, I wonder, under what input conditions could one assume that an algorithm for this problem can’t (or can) return a valid scaling factor?

If no known algorithms to this problem exist, are there any known classes of “scaling algorithms” that may solve a similar problems?

How can I predict javascript Math.random method given integers?

I know this is possible because people have mentioned doing it. Given the XorShift128+ algorithm, how can I predict the next numbers given 15 integers generated through Math.floor(Math.random() * (max - min +1) + min). I have tried modifying this script https://github.com/TACIXAT/XorShift128Plus into this https://gist.github.com/jgc37/6456222408f17a874bd4bdd8e6923771, however my code doesn’t work and is stuck solving infinitely. Any help would be appreciated.

Proof by contradiction – Only checking a right-neighbor in a sequence of pairwise distinct integers is sufficient to identify the first local maximum

I’m trying to figure out if my proof is valid, I think it makes intuitive sense but am worried I’m missing something. Any help would be much appreciated!

Question

A peak element is an element that is greater than its neighbors.  Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.  The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.  You may imagine that nums[-1] = nums[n] = -∞.  Example 1:  Input: nums = [1,2,3,1] Output: 2 Explanation: 3 is a peak element and your function should return the index number 2.  Example 2:  Input: nums = [1,2,1,3,5,6,4] Output: 1 or 5  Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6. 

Solution

public int findPeakElement(int[] nums) {     for (int i = 0; i < nums.length-1; i++) {         if (nums[i] > nums[i + 1]) {             return i;         }     }     return nums.length - 1; } 

Why don’t you have to check the left neighbor at each element?

Assume towards a contradiction that we are iterating through nums, yet to discover a peak, and we come across and element at index i whose right-neighbor at index i+1 is strictly smaller. If the element at index i were not a peak then the element at index i-1 would have to be strictly larger. Then we have that

nums[i-1] > nums[i] > nums[i+1] 

This then implies that nums[i+1] is the last element in a strictly decreasing sequence of elements (that we’ve seen), the start of which must be a peak (either the sequence starts at index 0 or it starts at index k, 0 < k < i). This contradicts our assumption, therefore the first element whose right-neighbor is strictly smaller is a local peak.