Google OA for Summer 2025 Internship

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.

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.