Given an Integer N. What Is the Smallest Integer Greater Than N That Only Has 0 or 1 as Its Digits

Given an integer N. What is the smallest integer greater than N that only has 0 or 1 as its digits?

Increment N,
Starting from the left, scan until you find a digit above 1. Increment the partial number before it and zero out the rest.

E.g.

12 -> 13 -> 1|3 -> 10|0
101 -> 102 -> 10|2 -> 11|0
109 -> 110 -> 111|
111 -> 112 -> 11|2 -> 100|0
198 -> 199 -> 1|99 -> 10|00
1098 -> 1099 -> 10|99 -> 11|00
10203 -> 10204 -> 10|204 -> 11|000
111234 -> 111235 -> 111|235 -> 1000|000
...

Proof:

The requested number must be at least N+1, this is why we increment. We are now looking for a number greater or equal.

Let us call the prefix the initial 0/1 digits and suffix what comes after. We must replace the first digit of the suffix by a zero and set a larger prefix. The smallest prefix that fits is the current prefix plus one. And the smallest suffix that fits is all zeroes.

Update:

I forgot to specify that the prefix must be incremented as a binary number, otherwise forbidden digits could appear.

Given an integer N. What is the smallest integer greater than N in java

Here is one approach.

Starting with the least N significant digits. N starts with 2. Save a copy.
then create all permutations of those N digits.
join them into a String and put in a TreeMap<String>
if there exists a next higher value of the original N digits, return the new value
with the new ending concatenated to the original.
else, increase N by one and repeat the process.

public class NextLargestInteger {
    public static void main(String[] args) {

Generate 10 random numbers.

        Random r = new Random();
        for (int i = 0; i < 10; i++) {
          int val = r.nextInt(Integer.MAX_VALUE);
          System.out.printf("%-12s   %-12s%n",val,nextHighest(Integer.toString(val)));
        }

Prints something like

1446553155     1446553[515]
1801279982     18012[82799]
1894877459     18948774[95]
805018669      8050186[96] 
521703779      5217037[97] 
1926164416     19261644[61]
1236907656     12369076[65]
1326860288     1326860[828]
1049149602     10491496[20]
1516995584     1516995[845]

The brackets on the right show what endings were permuted to get the minimum

The primary method.

    public static String nextHighest(String e) {
        char[] digits = e.toCharArray();
        // start two digits from the end
        int i = digits.length - 2;
        // tree set to store the permuted strings
        NavigableSet<String> set = new TreeSet<>();
        for (; i >= 0; i--) {
            
            // the last N digits
            char[] shortList =
                    Arrays.copyOfRange(digits, i, digits.length);

            // save a copy of the original N digit ending
            String originalTail = new String(shortList);

            permute(shortList, digits.length - i, set);
            
            // get the next higher ending from the set
            String minTail = set.higher(originalTail);
            // if it exists, return the value.
            if (minTail != null) {
                String head =
                        new String(Arrays.copyOfRange(digits, 0, i));
                return String.format("%s[%s]", head, minTail);
            }
            // clear the set and try a larger ending.
            set.clear();
        }
        // no success, return the original value.
        return e;
    }

Utility method to permute the character array

    public static void permute(char[] elements, int length,
            Set<String> vals) {
        if (length == 1) {
            vals.add(new String(elements));
        } else {
            for (int i = 0; i < length; i++) {
                permute(elements, length - 1, vals);
                if (length % 2 == 1) {
                    swap(elements, 1, length - 1);
                } else {
                    swap(elements, i, length - 1);
                }
            }
        }
        
    }

Utility method to swap array elements.

    public static void swap(char[] list, int i, int j) {
        char temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

Algorithm for finding the smallest +ve integer greater than a given number that has the same binary weight as given integer

This operation is sometimes called "snoob". Here is a bunch of approaches from the Hacker's Delight book. Probably the best would be to use Integer.numberOfTrailingZeros which likely compiles to a hardware instruction (untested):

int snoob1(int x) {
   int smallest, ripple, ones;  // x = xxx0 1111 0000
   smallest = x & -x;           //     0000 0001 0000
   ripple = x + smallest;       //     xxx1 0000 0000
   ones = x ^ ripple;           //     0001 1111 0000
   ones = ones >>> (2 + Integer.numberOfTrailingZeros(x)); //     0000 0000 0111
   return ripple | ones;        //     xxx1 0000 0111
}

(there might also be an issue with possible overflow in the "2+" part, since in Java shift counts are modulo 32)

Find the smallest positive integer that does not occur in a given sequence

If the expected running time should be linear, you can't use a TreeSet, which sorts the input and therefore requires O(NlogN). Therefore you should use a HashSet, which requires O(N) time to add N elements.

Besides, you don't need 4 loops. It's sufficient to add all the positive input elements to a HashSet (first loop) and then find the first positive integer not in that Set (second loop).

int N = A.length;
Set<Integer> set = new HashSet<>();
for (int a : A) {
    if (a > 0) {
        set.add(a);
    }
}
for (int i = 1; i <= N + 1; i++) {
    if (!set.contains(i)) {
        return i;
    }
}

How many numbers are required to make the returned values equal to integer N?

Here is a function that has constant storage and runs in time of order log(x). I cannot think that smaller storage or order of running time is possible.

The key idea is to treat x similar to a base-5 number. One way to find the base-5 representation of a number n is to find the first power of 5 that exceeds n, then keep decreasing that power of 5 and find how many of those fit into the number n. My routine is similar to that but removes the sums-of-exponents-of-5 rather than powers of 5. Finding the sum-of-exponents-of-n is easy for increasing powers of 5 due to a simple recurrence relation. There probably is a direct way to find the desired power of 5, but the second half of my function is slower than that so optimizing the first half of my function would not be much of an improvement.

I have tested this routine for values of x up to 10,000 and it checks. It is very fast, beyond x=10**100, though checking those results is very slow. Note that I prefer to use the parameter n for an integer value rather than your x.

Let me know if you need more explanation.

def smallestsumexp5s(n):
    """Return the smallest integer whose sum of the exponents of 5 in
    the prime decomposition of i for 1 <= i <= n is greater than or
    equal to n.
    """
    # Find the power of 5 whose sum passes n
    powerof5 = 5
    sumofexpsof5 = 1
    while sumofexpsof5 <= n:
        powerof5 *= 5
        sumofexpsof5 = sumofexpsof5 * 5 + 1
    # Cut off pieces of the target to find the desired integer
    remains = n
    result = 0
    while remains > 0:
        # Back off to the previous power of 5
        powerof5 //= 5
        sumofexpsof5 //= 5
        # Cut off pieces of the remaining number
        q, remains = divmod(remains, sumofexpsof5)
        # Adjust the accumulated result
        result += q * powerof5
    return result

returns the smallest positive integer (greater than 0) that does not occur in Array

using System.Linq;

int smallestNumber = Enumerable.Range(1, 100000).Except(A).Min();

Python given an array A of N integers, returns the smallest positive integer (greater than 0) that does not occur in A in O(n) time complexity

Testing for the presence of a number in a set is fast in Python so you could try something like this:

def minpositive(a):
    A = set(a)
    ans = 1
    while ans in A:
       ans += 1
    return ans

Smallest integer larger than lg N

Have any problem just tracing this on sample input?

step 1) N = 10, lgN = 0
step 2) N = 5,  lgN = 1
step 3) N = 2,  lgN = 2
step 4) N = 1,  lgN = 3
step 5) N = 0,  lgN = 4

lgN is 4 in the end. That's the smallest integer larger than log(2, 10)

Build smallest number larger than K using only allowed digits

Algorithm:

Let me introduce some variables:

k_digits - the number of digits in the number K.

First of all, we can observe that our resulting number will have k_digits or k_digits + 1. If it's not clear yet, I will explain it in more details in the end.

Let's start from assuming that the answer will have the k_digit digits.

We can split our main problem into a few smaller (and then receive the answer to the initial problem by combining the solutions to the subproblems). The statement of the subproblem will sound as following:

What is the smallest number is larger than K WITHOUT last digit.

Can we compose the number K without last digit from the digits we are allowed to use?

Let's assume we have a solution to both this problem. Then we need to find the answer to the initial problem. We can do this in the following way:

a) If the answer to the subproblem 2 is true (we can compose without last digit). Then we should try to add the smallest available digit from the set to the end of that number so it is larger than K. What we actually do - we try to replace the last digit of the initial K with the larger one from allowed set. Let's call this new number answer1.

b) Add the smallest available number from the set to the end of the number from the first subproblem. This number will be larger than K as its prefix is larger. Let's call this number answer2.

c) At the final step we should compare answer1 (if it exists) and answer2, and pick the smallest. This will be the answer to the initial question.

Well, now I hope it is clear how we combine the answer from the subproblems.
So, now I will explain how to find the solution to the subproblems.

Let's start from the second subproblem. It is easy - we just check if we have in our allowed set all digits of the number K (without last one).

Now the first subproblem. You may notice that this subproblem is equal to the initial problem, but with smaller K. So, we can solve this "recursively". The base case here will be single-digit K. We can say the answer directly, when we have only one digit - just to search our set for the digit larger the digit of the K.

Also, notice, at some point we may not have the answer to the subproblem 1. This means that we cannot compose the number of length k_digits that is larger than K. But, in this case, we can always compose the number with k_digits + 1. Just to select the smallest digit from the allowed set (k_digits + 1) times. Special case: zeros.

Example:

allowed_set=[4,5]
K = 435

We can see that we can spit our initial problem to subproblem, where K = 43.
The solution to the second subproblem will be false as we aren't allowed to use digit 3. The solution to the first subproblem we will try to find in the following way - splitting this again to the two subproblems, where K = 4. In this case, the answer to the first subproblem will be 5, and to the second subproblem will be 4. We can compose the answer to the case K = 43 as following: answer1 = 44, answer2 = 54. The answer1 is smaller, so, this is actually the answer to the case when K = 43. Then, to find the answer for K = 435 we only can add the 4 to the end of the 44. So, the answer is 444.

It may be not the best example, but I hope it illustrates my answer. Ask, if you have any additional comments.

Given an Integer N. What Is the Smallest Integer Greater Than N That Only Has 0 or 1 as Its Digits