Java 中算术级数中的缺失数字

2024 年 9 月 26 日 | 阅读 7 分钟

这是一个非常有趣的问题，经常出现在 Google、Amazon、TCS、Accenture 等顶级 IT 公司的面试中。通过解决这个问题，面试官希望考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将使用不同的方法和逻辑来在 Java 中找到等差数列中的缺失数字。此外，我们还将为此创建 Java 程序。

问题陈述

给定一个数组。该数组包含一些表示等差数列的数字。在等差数列中，缺少一个数字。任务是找到这个缺失的数字。

示例 1

输入

int arr[] = {3, 5, 7, 9, 11, 15, 17, 19}

输出 13

解释：如果我们在输入数组中数字 11 之后插入数字 13，则等差数列就完整了。因此，答案是 13

示例 2

输入

int arr[] = {1, 7, 13, 19, 31, 37, 43}

输出 25

解释：如果我们在输入数组中数字 19 之后插入数字 25，则等差数列就完整了。因此，答案是 25。

示例 3

输入

int arr[] = {25, 18, 4, -3, -10, -17, -24}

输出 11

解释：如果我们在输入数组中数字 18 之后插入数字 11，则等差数列就完整了。因此，答案是 11。

问题解决方案

使用等差数列公式

一个等差数列的数字之和，其首项为 a1，末项为 an，

总项数为 n 时：Sn = (n x (a1 + an) ) / 2。因此，我们可以计算输入数组的和。这是因为我们知道输入数组的首项、末项和大小。如果我们参考示例 1，我们得到

S9 = (9 x (3 + 19)) / 2 = (9 x 22) / 2 = 198 / 2 = 99 (9 是包含缺失元素的输入数组的大小)

现在，遍历数组并找到现有元素的和。我们得到

元素之和：3 + 5 + 7 + 9 + 11 + 15 + 17 + 19 = 86

现在，用 S8 减去输入数组元素的和。我们得到 99 - 86 = 13，这是等差数列的缺失元素。以下程序实现了相同的概念。

文件名：MissingElementAP.java

public class MissingElementAP 
{
public int findMissingEle(int inputArr[], int size)
{
    // for storing the sum of the elements
    // present in the array
    int sumOfEle = 0;
    // for storing the sum using the AP sum formula
    int APSum = 0;
    // sum of the elements of the array, including the missing element
    // using the sum of the elements of an Arithmetic Progression Formula
    // size + 1 because we have to include the missing element in the input array
    APSum = ((size + 1) * (inputArr[0] + inputArr[size - 1])) / 2;
    // loop for computing the sum of elements
    // present in the input array
    for(int i = 0; i < size; i++)
    {
        sumOfEle = sumOfEle + inputArr[i];
    }
    // finding the missing element
    int missingEle = APSum - sumOfEle;
    // returning the missing element
    return missingEle;
}
// main method
public static void main(String[] argvs) 
{
// creating an object of the class MissingElementAP
MissingElementAP obj = new MissingElementAP();
// input 1
int apArr[] = {3, 5, 7, 9, 11, 15, 17, 19};
int size = apArr.length;
int ans = obj.findMissingEle(apArr, size);
System.out.println("For the input array: ");
for(int k = 0; k < size; k++)
{
    System.out.print(apArr[k] + " ");
}
System.out.println( );
System.out.println("The missing element is: " + ans);
System.out.println( "\n" );
// input 2
int apArr1[] = {1, 7, 13, 19, 31, 37, 43};
size = apArr1.length;
ans = obj.findMissingEle(apArr1, size);
System.out.println("For the input array: ");
for(int k = 0; k < size; k++)
{
    System.out.print(apArr1[k] + " ");
}
System.out.println( );
System.out.println("The missing element is: " + ans);
System.out.println( "\n" );
// input 3
int apArr2[] = {25, 18, 4, -3, -10, -17, -24};
size = apArr2.length;
ans = obj.findMissingEle(apArr2, size);
System.out.println("For the input array: ");
for(int k = 0; k < size; k++)
{
    System.out.print(apArr2[k] + " ");
}
System.out.println( );
System.out.println("The missing element is: " + ans);
}
}
<p><strong>Output:</strong></p>
<div class="codeblock3"><pre>
For the input array: 
3 5 7 9 11 15 17 19 
The missing element is: 13


For the input array: 
1 7 13 19 31 37 43 
The missing element is: 25


For the input array: 
25 18 4 -3 -10 -17 -24 
The missing element is: 11
</pre></div>
<p><strong>Complexity Analysis:</strong> Since the program is using a for-loop for computing the sum of elements, the time complexity of the program is O(n), where n is the total number of elements present in the array. The space complexity of the program is constant, i.e., O(1).</p>
<h3 class="h3">Using Binary Search</h3>
<p>Observe the examples mentioned above. One can see that elements of the input array are either in increasing order or in decreasing order. Whenever such a kind of pattern is observed, one can use binary search.</p>
<p>Go to the middle element and compute the difference between the middle and next to the middle element. If it is not equal to the common difference of the arithmetic progression, then the missing element lies between mid and mid + 1. If the middle element is equal to the (s / 2)th term of the arithmetic progression series, then the missing element is in the right half of the input array; otherwise in the left half. The following program illustrates the same.</p>
<p><strong>FileName:</strong> MissingElementAP1.java</p>
<div class="codeblock"><textarea name="code" class="java">
public class MissingElementAP1
{
// the following method implements the binary 
// search with the help of recursion to find the 
// missing element in the arithmetic progression
public int findMissingUtility(int arr[], int l, int h, int difference)
{
// There has to be atleast two elements
// for computing the missing element
if (h <= l)
{
return Integer.MAX_VALUE;
}
// Finding the middle element index
int m = l + (h - l) / 2;
// The element just after the middle element is missing.
// The arr[mid+1] must exist, because we return when
// (l == hi) and take the floor of (h - l) / 2
if (arr[m + 1] - arr[m] != difference)
{
return (arr[m] + difference);
}
// The element just before mid is missing
if (m > 0 && arr[m] - arr[m - 1] != difference)
{
return (arr[m - 1] + difference);
}
// If the elements till the mid follow
// AP, then apply recursion on the right half
if (arr[m] == arr[0] + m * difference)
{
return findMissingUtility(arr, m + 1, h, difference);
}
// Else applying recursion on the left half
return findMissingUtility(arr, l, m - 1, difference);
}
// The method uses the method findMissingUtility()
// for finding the element that is missing in AP.
// The method only the considers that the 
// common difference of the arithmetic progression is
// an integer.
public int findMissing(int arr[], int n)
{
// Since only one element is missing
// we can use the last and first element
// for computing the common difference of the
// arithemtic progression
int commonDiff = (arr[n - 1] - arr[0]) / n;
// Applying Binary search for the missing
// number using the above calculated diff
return findMissingUtility(arr, 0, n - 1, commonDiff);
}
// main method
public static void main(String[] argvs) 
{
// creating an object of the class MissingElementAP1
MissingElementAP1 obj = new MissingElementAP1();
// input 1
int apArr[] = {3, 5, 7, 9, 11, 15, 17, 19};
int size = apArr.length;
int ans = obj.findMissing(apArr, size);
System.out.println("For the input array: ");
for(int k = 0; k < size; k++)
{
System.out.print(apArr[k] + " ");
}
System.out.println( );
System.out.println("The missing element is: " + ans);
System.out.println( "\n" );
// input 2
int apArr1[] = {1, 7, 13, 19, 31, 37, 43};
size = apArr1.length;
ans = obj.findMissing(apArr1, size);
System.out.println("For the input array: ");
for(int k = 0; k < size; k++)
{
System.out.print(apArr1[k] + " ");
}
System.out.println( );
System.out.println("The missing element is: " + ans);
System.out.println( "\n" );
// input 3
int apArr2[] = {25, 18, 4, -3, -10, -17, -24};
size = apArr2.length;
ans = obj.findMissing(apArr2, size);
System.out.println("For the input array: ");
for(int k = 0; k < size; k++)
{
System.out.print(apArr2[k] + " ");
}
System.out.println( );
System.out.println("The missing element is: " + ans);
}
}

输出

For the input array: 
3 5 7 9 11 15 17 19 
The missing element is: 13


For the input array: 
1 7 13 19 31 37 43 
The missing element is: 25


For the input array: 
25 18 4 -3 -10 -17 -24 
The missing element is: 11

复杂度分析：由于程序使用二分查找，因此程序的时间复杂度为 O(n)，其中 n 是输入数组中存在的元素总数。程序不使用任何辅助空间。因此，程序的空间复杂度是常数，即 O(1)。

下一主题Java 中山脉数组的峰值索引问题

Java 中算术级数中的缺失数字

问题陈述

问题解决方案

使用等差数列公式

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中算术级数中的缺失数字

问题陈述

问题解决方案

使用等差数列公式

相关帖子

如何在 Java 中将时间戳转换为日期

查找数组中每个元素出现频率的 Java 程序

Java 从三叉树创建双向链表的程序

Java 中的最小激活灯泡问题

计算二叉树奇数层和偶数层节点和之差的 Java 程序

创建 n 个节点的循环链表并以逆序显示它的 Java 程序

Java 计算字符串中元音和辅音总数的程序

查找二叉树中最大距离节点的 Java 程序

如何在 Java 中将字符串转换为 long

Java 查找字符串所有子集的程序

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器