指定された配列から等差数列を形成できるかどうかを確認する

GfG Practice で試してみる ' title=

の配列が与えられると、 n 整数。タスクは、指定されたすべての要素を使用して等差数列を形成できるかどうかを確認することです。可能な場合は「はい」を出力し、そうでない場合は「いいえ」を出力します。

例:

入力: arr[] = {0 12 4 8}
出力: はい
指定された配列を {0 4 8 12} として再配置し、等差数列を形成します。

入力: arr[] = {12 40 11 20}
出力: いいえ

並べ替えの使用 - O(n Log n) 時間

アイデアは、指定された配列をソートすることです。並べ替え後、連続する要素間の差異が同じかどうかを確認します。すべての差が同じであれば等差数列が可能です。参照してください - 等差数列をチェックするプログラムこのアプローチの実装のために。

C++ ペア

カウントソートの使用 - O(n) 時間と O(n) スペース

指定された配列を変更できる場合、方法 3 で必要なスペースを削減できます。

Javaのリンクリスト

最小の要素と 2 番目に小さい要素を見つけます。
d = Second_smallest - 最小値を求めます
すべての要素から最小の要素を減算します。
ここで、与えられた配列が AP を表す場合、すべての要素は i*d の形式でなければなりません (i は 0 から n-1 まで変化します)。
すべての縮小要素を d で 1 つずつ除算します。 d で割り切れない要素がある場合は false を返します。
ここで、配列が AP を表す場合、それは 0 から n-1 までの数値の順列でなければなりません。これは、カウンティングソートを使用して簡単に確認できます。

以下はこのメソッドの実装です。

C++

// C++ program to check if a given array // can form arithmetic progression #include    using namespace std; // Checking if array is permutation  // of 0 to n-1 using counting sort bool countingsort(int arr[] int n) {  int count[n] = { 0 };    // Counting the frequency  for (int i = 0; i < n; i++) {  count[arr[i]]++;  }    // Check if each frequency is 1 only  for (int i = 0; i <= n-1; i++) {  if (count[i] != 1)  return false;  }    return true; } // Returns true if a permutation of arr[0..n-1] // can form arithmetic progression bool checkIsAP(int arr[] int n) {  int smallest = INT_MAX second_smallest = INT_MAX;  for (int i = 0; i < n; i++) {    // Find the smallest and   // update second smallest  if (arr[i] < smallest) {  second_smallest = smallest;  smallest = arr[i];  }    // Find second smallest  else if (arr[i] != smallest  && arr[i] < second_smallest)  second_smallest = arr[i];  }  // Find the difference between smallest and second  // smallest  int diff = second_smallest - smallest;  for (int i = 0; i < n; i++) {  arr[i]=arr[i]-smallest;  }    for(int i=0;i<n;i++)  {  if(arr[i]%diff!=0)  {  return false;  }  else  {  arr[i]=arr[i]/diff;  }  }    // If array represents AP it must be a   // permutation of numbers from 0 to n-1.  // Check this using counting sort.  if(countingsort(arrn))  return true;  else  return false; } // Driven Program int main() {  int arr[] = { 20 15 5 0 10 };  int n = sizeof(arr) / sizeof(arr[0]);  (checkIsAP(arr n)) ? (cout << 'Yes' << endl)  : (cout << 'No' << endl);  return 0;  // This code is contributed by Pushpesh Raj }

Java

// Java program to check if a given array // can form arithmetic progression import java.io.*; class GFG {  // Checking if array is permutation  // of 0 to n-1 using counting sort  static boolean countingsort(int arr[] int n)  {  int[] count = new int[n];  for(int i = 0; i < n; i++)  count[i] = 0;  // Counting the frequency  for (int i = 0; i < n; i++) {  count[arr[i]]++;  }  // Check if each frequency is 1 only  for (int i = 0; i <= n-1; i++) {  if (count[i] != 1)  return false;  }  return true;  }  // Returns true if a permutation of arr[0..n-1]  // can form arithmetic progression  static boolean checkIsAP(int arr[] int n)  {  int smallest = Integer.MAX_VALUE second_smallest = Integer.MAX_VALUE ;  for (int i = 0; i < n; i++) {  // Find the smallest and  // update second smallest  if (arr[i] < smallest) {  second_smallest = smallest;  smallest = arr[i];  }  // Find second smallest  else if (arr[i] != smallest  && arr[i] < second_smallest)  second_smallest = arr[i];  }  // Find the difference between smallest and second  // smallest  int diff = second_smallest - smallest;  for (int i = 0; i < n; i++) {  arr[i] = arr[i] - smallest;  }  for(int i = 0; i < n; i++)  {  if(arr[i] % diff != 0)  {  return false;  }  else  {  arr[i] = arr[i]/diff;  }  }  // If array represents AP it must be a  // permutation of numbers from 0 to n-1.  // Check this using counting sort.  if(countingsort(arrn))  return true;  else  return false;  }  // Driven Program  public static void main (String[] args)  {  int arr[] = { 20 15 5 0 10 };  int n = arr.length;  if(checkIsAP(arr n))   System.out.println('Yes');  else System.out.println('No');  } } // This code is contributed by Utkarsh

Python

# Python program to check if a given array # can form arithmetic progression import sys # Checking if array is permutation  # of 0 to n-1 using counting sort def countingsort( arr n): count = [0]*n; # Counting the frequency for i in range(0 n): count[arr[i]] += 1; # Check if each frequency is 1 only for i in range(0 n - 1): if (count[i] != 1): return False; return True; # Returns true if a permutation of arr[0..n-1] # can form arithmetic progression def checkIsAP( arr n): smallest = sys.maxsize; second_smallest = sys.maxsize; for i in range(0n): # Find the smallest and  # update second smallest if (arr[i] < smallest) : second_smallest = smallest; smallest = arr[i]; # Find second smallest elif (arr[i] != smallest and arr[i] < second_smallest): second_smallest = arr[i]; # Find the difference between smallest and second # smallest diff = second_smallest - smallest; for i in range(0n): arr[i]=arr[i]-smallest; for i in range(0n): if(arr[i]%diff!=0): return False; else: arr[i]=(int)(arr[i]/diff); # If array represents AP it must be a  # permutation of numbers from 0 to n-1. # Check this using counting sort. if(countingsort(arrn)): return True; else: return False; # Driven Program arr = [ 20 15 5 0 10 ]; n = len(arr); if(checkIsAP(arr n)): print('Yes'); else: print('NO'); # This code is contributed by ratiagrawal.

using System;  class GFG  {  // Checking if array is permutation  // of 0 to n-1 using counting sort  static bool CountingSort(int[] arr int n)  {  // Counting the frequency  int[] count = new int[n];  for (int i = 0; i < n; i++)  {  count[arr[i]]++;  }  // Check if each frequency is 1 only  for (int i = 0; i <= n - 1; i++)  {  if (count[i] != 1)  {  return false;  }  }  return true;  }// Returns true if a permutation of arr[0..n-1]  // can form arithmetic progression  static bool CheckIsAP(int[] arr int n)  {// Find the smallest and  // update second smallest  int smallest = int.MaxValue;  int secondSmallest = int.MaxValue;  for (int i = 0; i < n; i++)  {  if (arr[i] < smallest)  {  secondSmallest = smallest;  smallest = arr[i];  }  else if (arr[i] != smallest && arr[i] < secondSmallest)  {  secondSmallest = arr[i];  }  }  int diff = secondSmallest - smallest;  for (int i = 0; i < n; i++)  {  arr[i] = arr[i] - smallest;  }  for (int i = 0; i < n; i++)  {  if (arr[i] % diff != 0)  {  return false;  }  else  {  arr[i] = arr[i] / diff;  }  } // If array represents AP it must be a  // permutation of numbers from 0 to n-1.  // Check this using counting sort.  if (CountingSort(arr n))  {  return true;  }  else  {  return false;  }  } // Driven Program  static void Main(string[] args)  {  int[] arr = new int[] { 20 15 5 0 10 };  int n = arr.Length;  Console.WriteLine(CheckIsAP(arr n) ? 'Yes' : 'No');  }  }

JavaScript

// Javascript program to check if a given array // can form arithmetic progression // Checking if array is permutation  // of 0 to n-1 using counting sort function countingsort( arr n) {  let count=new Array(n).fill(0);    // Counting the frequency  for (let i = 0; i < n; i++) {  count[arr[i]]++;  }    // Check if each frequency is 1 only  for (let i = 0; i <= n-1; i++) {  if (count[i] != 1)  return false;  }    return true; } // Returns true if a permutation of arr[0..n-1] // can form arithmetic progression function checkIsAP( arr n) {  let smallest = Number.MAX_SAFE_INTEGER second_smallest = Number.MAX_SAFE_INTEGER;  for (let i = 0; i < n; i++) {    // Find the smallest and   // update second smallest  if (arr[i] < smallest) {  second_smallest = smallest;  smallest = arr[i];  }    // Find second smallest  else if (arr[i] != smallest  && arr[i] < second_smallest)  second_smallest = arr[i];  }  // Find the difference between smallest and second  // smallest  let diff = second_smallest - smallest;  for (let i = 0; i < n; i++) {  arr[i]=arr[i]-smallest;  }    for(let i=0;i<n;i++)  {  if(arr[i]%diff!=0)  {  return false;  }  else  {  arr[i]=arr[i]/diff;  }  }    // If array represents AP it must be a   // permutation of numbers from 0 to n-1.  // Check this using counting sort.  if(countingsort(arrn))  return true;  else  return false; } // Driven Program let arr = [20 15 5 0 10 ]; let n = arr.length; (checkIsAP(arr n)) ? (console.log('Yesn'))  : (console.log('Non'));    // // This code was contributed by poojaagrawal2.

出力

Yes

時間計算量 - O(n)
補助スペース - O(n)

シングルパスによるハッシュ - O(n) 時間と O(n) スペース

基本的な考え方は、配列の最大要素と最小要素を見つけることによって AP の共通の違いを見つけることです。その後、最大値から開始して、この新しい値がハッシュマップに存在するかどうかを確認しながら、共通の差分だけ値を減らし続けます。いずれかの時点で値がハッシュセットに存在しない場合は、ループを中断します。ループが中断された後の理想的な状況は、n 個の要素がすべてカバーされており、yes の場合は true を返し、そうでない場合は false を返します。

C++

// C++ program for above approach #include    using namespace std; bool checkIsAP(int arr[] int n) {  unordered_set<int> st;  int maxi = INT_MIN;  int mini = INT_MAX;  for (int i=0;i<n;i++) {  maxi = max(arr[i] maxi);  mini = min(arr[i] mini);  st.insert(arr[i]);  }    // FINDING THE COMMON DIFFERENCE  int diff = (maxi - mini) / (n - 1);  int count = 0;  // CHECK TERMS OF AP PRESENT IN THE HASHSET  while (st.find(maxi)!=st.end()) {  count++;  maxi = maxi - diff;  }    if (count == n)  return true;  return false; } // Driver Code int main() {  int arr[] = { 0 12 4 8 };  int n = 4;  cout << boolalpha << checkIsAP(arr n);  return 0; } // This code is contributed by Rohit Pradhan

Java

/*package whatever //do not write package name here */ import java.io.*; import java.util.*; class GFG {  public static void main(String[] args)  {  int[] arr = { 0 12 4 8 };  int n = arr.length;  System.out.println(checkIsAP(arr n));  }  static boolean checkIsAP(int arr[] int n)  {  HashSet<Integer> set = new HashSet<Integer>();  int max = Integer.MIN_VALUE;  int min = Integer.MAX_VALUE;  for (int i : arr) {  max = Math.max(i max);  min = Math.min(i min);  set.add(i);  }    // FINDING THE COMMON DIFFERENCE  int diff = (max - min) / (n - 1);  int count = 0;  // CHECK IF TERMS OF AP PRESENT IN THE HASHSET   while (set.contains(max)) {  count++;  max = max - diff;  }  if (count == arr.length)  return true;  return false;  } }

Python

import sys def checkIsAP(arr n): Set = set() Max = -sys.maxsize - 1 Min = sys.maxsize for i in arr: Max = max(i Max) Min = min(i Min) Set.add(i) # FINDING THE COMMON DIFFERENCE diff = (Max - Min) // (n - 1) count = 0 # CHECK IF TERMS OF AP PRESENT IN THE HASHSET  while (Max in Set): count += 1 Max = Max - diff if (count == len(arr)): return True return False # driver code arr = [ 0 12 4 8 ] n = len(arr) print(checkIsAP(arr n)) # This code is contributed by shinjanpatra

using System; using System.Collections.Generic; public class GFG  {  // C# program for above approach  static bool checkIsAP(int[] arr int n)  {  HashSet<int> st = new HashSet<int>();  int maxi = int.MinValue;  int mini = int.MaxValue;  for (int i = 0; i < n; i++) {  maxi = Math.Max(arr[i] maxi);  mini = Math.Min(arr[i] mini);  st.Add(arr[i]);  }    // FINDING THE COMMON DIFFERENCE  int diff = (maxi - mini) / (n - 1);  int count = 0;  // CHECK IF TERMS OF AP PRESENT IN THE HASHSET   while (st.Contains(maxi)) {  count++;  maxi = maxi - diff;  }  if (count == n) {  return true;  }  return false;  }  // Driver Code  internal static void Main()  {  int[] arr = { 0 12 4 8 };  int n = 4;  Console.Write(checkIsAP(arr n));  }  // This code is contributed by Aarti_Rathi }

JavaScript

function checkIsAP(arr n){  set = new Set()  let Max = Number.MIN_VALUE  let Min = Number.MAX_VALUE  for(let i of arr){  Max = Math.max(i Max)  Min = Math.min(i Min)  set.add(i)  }    // FINDING THE COMMON DIFFERENCE  let diff = Math.floor((Max - Min) / (n - 1))  let count = 0  // CHECK IF TERMS OF AP PRESENT IN THE HASHSET   while (set.has(Max)){  count += 1  Max = Max - diff  }  if (count == arr.length)  return true  return false } // driver code let arr = [ 0 12 4 8 ] let n = arr.length console.log(checkIsAP(arr n))

出力

true

クイズの作成