The Sparsest Number in Between
Source: aizu

The Sparsest Number in Between

You are given a pair of positive integers $a$ and $b$ ($a \leq b$). Among those integers between $a$ and $b$, inclusive, your task is to find the sparsest one, that is, the one with the least number of 1's in its binary representation. If there are two or more such integers, you should find the smallest among them.

Suppose, for instance, that $a = 10$ and $b = 13$. The integers between $a$ and $b$, inclusive, are 10, 11, 12, and 13, and their binary representations are 1010, 1011, 1100, and 1101, respectively. Thus, in this case, the answer is 10, since 10 and 12 have the least number of 1's in their binary representations and 10 is smaller than 12.

Input

The input consists of a single test case of the following format.

$a$ $b$


Here, $a$ and $b$ ($a \leq b$) are integers between $1$ and $10^{18}$, inclusive.

Output

Output a line containing the smallest among the sparsest integers between $a$ and $b$, inclusive.

Sample Input 1
10 13

Sample Output 1
10

Sample Input 2
11 15

Sample Output 2
12

Sample Input 3
11 20

Sample Output 3
16

Sample Input 4
1 1000000000000000000

Sample Output 4
1

Sample Input 5
9876543210 9876543210

Sample Output 5
9876543210


C++ solution:
#include <iostream>
#include <climits>

using namespace std;

long long countOnes(long long n) {
    long long count = 0;
    while (n > 0) {
        count += n & 1;
        n >>= 1;
    }
    return count;
}

long long findSparsestNumber(long long a, long long b) {
    long long sparsest = a;
    long long minOnes = countOnes(a);

    // Check if there's a power of two in the range
    for (int i = 0; i <= 60; ++i) {
        long long power = 1LL << i;
        if (a <= power && power <= b) {
            return power;
        }
    }

    // If no power of two is found, find the number with the least number of 1's
    // Optimize by checking numbers with minimal 1's first
    for (long long i = a; i <= b; ++i) {
        long long currentOnes = countOnes(i);
        if (currentOnes < minOnes) {
            minOnes = currentOnes;
            sparsest = i;
        } else if (currentOnes == minOnes && i < sparsest) {
            sparsest = i;
        }
        // Early exit if the minimal possible is found
        if (minOnes == 1) {
            break;
        }
    }

    return sparsest;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << findSparsestNumber(a, b) << endl;
    return 0;
}

Go solution:
package main

import (
	"fmt"
	"math/bits"
)

func main() {
	var a, b uint64
	fmt.Scan(&a, &b)

	// Check if there's a power of 2 between a and b
	for i := 0; i <= 63; i++ {
		power := uint64(1) << i
		if a <= power && power <= b {
			fmt.Println(power)
			return
		}
	}

	// If no power of 2 is found, find the number with the least 1 bits
	var temp uint64
	for i := 63; i >= 0; i-- {
		power := uint64(1) << i
		if a >= power && b >= power {
			temp += power
			a -= power
			b -= power
			// Check again for power of 2 in the new a and b
			for j := 0; j <= 63; j++ {
				newPower := uint64(1) << j
				if a <= newPower && newPower <= b {
					fmt.Println(newPower + temp)
					return
				}
			}
		}
	}

	// If all else fails, return the smallest number in the range
	fmt.Println(a + temp)
}

Java solution:
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        long a = scanner.nextLong();
        long b = scanner.nextLong();

        // Check for powers of two within the range [a, b]
        for (int i = 0; i <= 60; i++) {
            long power = 1L << i;
            if (a <= power && power <= b) {
                System.out.println(power);
                return;
            }
        }

        // If no power of two is found, find the highest power of two <= b
        int highestPower = 0;
        while ((1L << (highestPower + 1)) <= b) {
            highestPower++;
        }
        long highestPowerValue = 1L << highestPower;

        if (highestPowerValue >= a) {
            System.out.println(highestPowerValue);
            return;
        }

        // If no power of two is found, find the smallest number with the least number of 1's
        long minOnes = Long.MAX_VALUE;
        long result = a;
        for (long num = a; num <= b; num++) {
            long ones = Long.bitCount(num);
            if (ones < minOnes) {
                minOnes = ones;
                result = num;
            } else if (ones == minOnes && num < result) {
                result = num;
            }
        }
        System.out.println(result);
    }
}

JavaScript solution:
const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

rl.on('line', (input) => {
    const [aStr, bStr] = input.trim().split(' ');
    const a = BigInt(aStr);
    const b = BigInt(bStr);
    
    // Function to count the number of 1's in the binary representation of a number
    function countOnes(n) {
        let count = 0n;
        while (n > 0n) {
            count += n & 1n;
            n >>= 1n;
        }
        return count;
    }

    // Check if there's a power of 2 in the range [a, b]
    for (let i = 0n; i <= 70n; i++) {
        const power = 1n << i;
        if (power >= a && power <= b) {
            console.log(power.toString());
            rl.close();
            return;
        }
    }

    // If no power of 2 is found, find the number with the least number of 1's
    let minOnes = countOnes(a);
    let result = a;

    for (let num = a + 1n; num <= b; num++) {
        const currentOnes = countOnes(num);
        if (currentOnes < minOnes) {
            minOnes = currentOnes;
            result = num;
            // Early exit if the minimum possible ones is found
            if (minOnes === 1n) {
                break;
            }
        } else if (currentOnes === minOnes && num < result) {
            result = num;
        }
    }

    console.log(result.toString());
    rl.close();
});

Python solution:
a, b = map(int, input().split())

for i in range(70):
  if a <= pow(2, i) <= b:
    print(pow(2, i))
    exit()

temp = 0
for i in range(69, -1, -1):
  now = pow(2, i)
  if a >= now and b >= now:
    temp += now
    a -= now
    b -= now
    for j in range(70):
      if a <= pow(2, j) <= b:
        print(pow(2, j) + temp)
        exit()

print(a, b)

Ruby solution:
def count_ones(n)
  count = 0
  while n > 0
    count += n & 1
    n >>= 1
  end
  count
end

a, b = gets.split.map(&:to_i)

# First, check if there's a power of 2 between a and b
(0..60).each do |i|
  power = 1 << i
  if a <= power && power <= b
    puts power
    exit
  end
end

# If no power of 2 found, find the number with minimal Hamming weight
min_ones = Float::INFINITY
result = a

# Optimize by checking numbers with fewer bits first
max_bits = b.to_s(2).size
(1..max_bits).each do |bit_count|
  # Generate numbers with exactly bit_count bits and count ones
  (a..b).each do |num|
    next if num.to_s(2).size != bit_count
    ones = count_ones(num)
    if ones < min_ones
      min_ones = ones
      result = num
      # Early exit if we find a number with only one '1' (power of 2)
      break if min_ones == 1
    elsif ones == min_ones && num < result
      result = num
    end
  end
  break if min_ones == 1  # Can't get better than 1
end

puts result