Introduction

Google Online Assessment (OA) for the Summer Internship 2025 is a crucial part of the hiring process. This assessment tests your coding skills, problem-solving abilities, and your aptitude for tackling complex algorithms. One of the typical problems you might encounter is transforming a number into a palindromic binary form with the least number of operations. In this blog, we will delve into this problem and provide strategies to solve it efficiently.

Image description

Problem Statement

You are given a number ( N ) (0 <= ( N ) <= 2 * 10^9), and you can perform the following operation any number of times, including zero:

  • Increase or decrease the number by 1.

Your task is to find the minimum number of operations needed to make the binary form of ( N ) palindromic.

Example:

  • ( N = 6 ) (binary: 110)
  • Answer: 1
  • Explanation: You need to decrease ( N ) by 1 to make it 5, as the binary representation of 5 is palindromic (101), or you can increase ( N ) by 1 to make it 7, as its binary is also palindromic (111).

Understanding Palindromic Binary Numbers

A palindromic binary number reads the same forwards and backwards. For instance:

  • 101 (binary of 5)
  • 111 (binary of 7)

Approach to Solve the Problem

To solve this problem, we need to identify the nearest palindromic binary number to ( N ) and calculate the number of operations required to reach it. Here’s a step-by-step approach:

Step 1: Convert the Number to Binary

First, convert the given number ( N ) into its binary representation.

Step 2: Check for Palindromic Binary Numbers

Check if the binary representation is already palindromic. If it is, no operations are needed.

Step 3: Find the Nearest Palindromic Binary Numbers

If the binary representation is not palindromic, find the nearest palindromic binary numbers by incrementing and decrementing ( N ).

Step 4: Calculate the Number of Operations

Calculate the number of operations required to transform ( N ) into the nearest palindromic binary number.

Example Walkthrough

Let’s walk through the example given in the problem statement:

Example: ( N = 6 )

  1. Convert to Binary: ( N = 6 ) -> Binary: 110
  2. Check Palindromic: 110 is not palindromic.
  3. Find Nearest Palindromic:
    • Increment ( N ) by 1 -> ( N = 7 ) -> Binary: 111 (palindromic)
    • Decrement ( N ) by 1 -> ( N = 5 ) -> Binary: 101 (palindromic)
  4. Calculate Operations:
    • Increment: ( N = 6 ) to ( N = 7 ) -> 1 operation
    • Decrement: ( N = 6 ) to ( N = 5 ) -> 1 operation

Thus, the minimum number of operations is 1.

Implementation Strategy

To implement the solution, follow these steps:

  1. Convert Number to Binary: Use built-in functions to convert ( N ) to binary.
  2. Check Palindromic: Create a function to check if a binary string is palindromic.
  3. Find Nearest Palindromic: Increment and decrement ( N ) and check for palindromic binary strings.
  4. Calculate Operations: Return the minimum number of operations required.

Conclusion

Google OA for the Summer Internship 2025 challenges candidates with complex problems that test their coding and problem-solving skills. Understanding how to transform a number into a palindromic binary form with minimal operations is a valuable skill. By following the strategies outlined in this blog, you can efficiently tackle this problem and enhance your chances of success in the assessment.